後置から中置記法へ

Habréの逆ポーランド記法（記録）については、すでに述べています。 ご存知のように、数式の接尾辞表記におけるアレスタのすべての力。 よく知られている中置表記法を後置表記に変換する方法については、上記のウィキペディアの記事で詳しく説明されており、 アセンブラーでの実装も記載されています。 しかし、逆のアクションをどのように上げるかについての記事は見つかりませんでした。







おそらく最初に尋ねる質問は、「なぜこれが必要なのですか？」 ユーザーが入力した式を最適化し、挿入レコードに結果を表示する必要があることを想像してください。もちろん、アレスタを使用して最適化します。



さて、今ポイントに近い：

アルゴリズムの言葉による説明：

1. 数値を読み取った場合、それをスタックにプッシュします
2. 操作記号を読み取ると、次のようになります。
   
   
   • 私たちは2つのトップスタック要素を取ります
   • 最初の要素の操作の優先度が問題の操作の優先度よりも低い（そして0に等しくない）場合、括弧内の最初の要素を使用します
   • 同様に、2番目の要素について
   • 次の形式の行をスタックに書き込みます：2番目の要素+操作記号+ 1番目の要素
   
   
   
3. 行が完全にトラバースされた場合、結果はスタックの最上部の値になります

C ++実装

#include <string.h> #include <stdio.h> #include <stdlib.h> // <-- --> enum optype {power = 3, devide = 2, multiply = 2, minus = 1, plus = 1, null=0}; //   struct stack { char val[100]; //    optype type; //  ,      stack * next; } *head; // <--   --> void push(char[], optype); void push(stack *); stack * pop(); // <--   --> void fromRPN(char *, char *); // (RPN) Reverse polish notation int main() { char infix[100], postfix[100]; //     gets(infix); fromRPN(infix, postfix); printf("%s\n", postfix); system("PAUSE"); return 0; } void push(stack *t) { t->next = head; head = t; } void push(char str[], optype type) { stack *t; t = new stack; strcpy(t->val, str); t->type = type; t->next = head; head = t; } stack * pop() { stack *t; if(head == NULL) return NULL; t = head; head = t->next; return t; } void fromRPN(char * input, char * output) { char c, temp[100]; int p_temp=0; stack *h1, *h2; //        optype type; head = NULL; while(*input) { //     c = (*input); if(c>='0' && c<='9' || c=='.') { //     temp[p_temp++] = c; //      temp[p_temp] = '\0'; } else if(c==' ') { if(p_temp!=0) { push(temp, null); //     p_temp=0; } temp[0] = '\0'; //    } else if(c=='+' || c=='-'|| c=='*' || c=='/' || c=='^') { //    h1 = pop(); //    h2 = pop(); //    //    if(c=='+') type = plus; else if(c=='-') type = minus; else if(c=='*') type = multiply; else if(c=='/') type = devide; else if(c=='^') type = power; if(h2->type!=null && h2->type<type) { //    1-   temp[0]='('; temp[1] = '\0'; //     h2->val[strlen(h2->val)+2] = '\0'; h2->val[strlen(h2->val)+1] = c; //    h2->val[strlen(h2->val)] = ')'; } else { h2->val[strlen(h2->val)+1] = '\0'; h2->val[strlen(h2->val)] = c; } strcat(temp, h2->val); if(h1->type!=null && h1->type<type) { //    2-   strcat(temp, "("); h1->val[strlen(h1->val)+1] = '\0'; h1->val[strlen(h1->val)] = ')'; //     } strcat(temp, h1->val); strcpy(h2->val, temp); //        ,       delete h1; //    h2->type = type; //     push(h2); //      } input++; } strcpy(output, (pop())->val); //         }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

作業例

例として、Habrの記事の例から変換された式を使用します。

 : (8+2*5)/(1+3*2-4) : 8 2 5 * + 1 3 2 * + 4 - /  "8" : {"8", null=0}  "8" --: {"8", null=0}  "2" --: {"2", null=0}, {"8", null=0}  "5" --: {5, null=0}, {"2", null=0}, {"8", null=0}  "*" --: {"2*5", multiply=2}, {"8", null=0}  "+" --: {"8+2*5", plus=1}  "1" --: {"1", null=0}, {"8+2*5", plus=1}  "3" --: {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}  "2" --: {"2", null=0}, {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}  "*" --: {"3*2", multiply=2}, {"1", null=0}, {"8+2*5", plus=1}  "+" --: {"1+3*2", plus=1}, {"8+2*5", plus=1}  "4" --: {"4", null=0}, {"1+3*2", plus=1}, {"8+2*5", plus=1}  "-" --: {"1+3*2-4", minus=1}, {"8+2*5", plus=1}  "/" //    ,      --: {"(8+2*5)/(1+3*2-4)", devide=2} : (8+2*5)/(1+3*2-4)