質問: 演算子+、 - 、*、/とカッコ(演算子の自然優先を変更する場合もあれば変更しない場合もある)を含む算術式が与えられます。 a / b + f - (c + d)* e - a * cのような例が考えられます。オペランドと演算子を追跡するために、スタックされたリスト(リンクされたリストとして実装されている)を使用するように求められます。私のプログラムがどのように機能するかの例は、次のとおりです。 * aを読み、オペランドスタックをプッシュする * リード/、オペレータスタックを押す * bを読んで、オペランドスタックを押す * Read +:は/より優先度が低く、したがって: + オペランドスタックから2つのオペランド(aおよびb)をポップします。 + pop /オペレータスタックから + サブツリーを作成し、オペランドスタックをプッシュする + 演算子スタックは空であるため、その上に+を押します * fを読んで、オペランドスタックを押す * Read - :は+と同じ優先順位を持ちます: + オペランドスタックから2つのオペランドをポップする + pop演算子+演算子スタックから + 演算子+をルートとし、2つのオペランドを左右の子として持つツリーを作成する + 作成されたツリーのルートをオペランドスタックにプッシュバックする + 演算子スタックが空であるため、push-on 理解が難しい問題は、どのよう**にしてオペランドの優先順位**を区別できるかです。 ここに私が書いたコードの不完全なバージョンがあります: ``` #include #include #include typedef struct btnode Btree; typedef struct node s_Node; struct btnode { char info; Btree *left; Btree *right; }; struct node { char element; s_Node*next; }; typedef struct{ s_Node *top_stack; } stack_t; int IsOperator(char c); main () { FILE* fp; stack_t operands; stack_t operators; char c; operands=NewStack(); operators=NewStack(); fp= fopen ("Myfile.txt", "r"); if (fp== NULL) printf (" FILE COULD NOT BE OPENED"); else { c=getc(fp); while (!feof (fp)) { if ( c== ' '); else { printf ("Here is your character: %c\n", c); if (IsOperator (c)) Push (c, &operands); else if ( isalpha (c)) } c=getc(fp); } } } int IsOperator(char c) { switch(c) { case '+': case '-': case '/': case '*': return 1; default: return 0; } } stack_t NewStack() { stack_t *n_stack; n_stack=(stack_t*)malloc(sizeof(stack_t)); n_stack->top_stack=NULL; return (*n_stack); } int Push(char e, stack_t *q) { s_Node *nn; nn= (s_Node*)malloc(sizeof(s_Node)); if(Full(*q)) { printf("\n\t Stack is Full !! \n\n"); return 0; // return 0 if enstack NOT successful } else { nn->element=e; // Storing the elemnt read inside the the new node nn->next=q->top_stack; // Pointing the new node to the top of the stack q->top_stack=nn; // Changing the top of the stack return 1; } } ``` 前もって感謝します!
回答: 使用しているアルゴリズムでは、オペランドは優先順位がありません。しかし、ボトムアップ・シフト・パーサーでは、@WhozCraigがこの記事のコメントで以下のように述べているように、優先順位があります。 オペランドは常にオペランドスタックにプッシュされ、2がポップアウトされ、演算子で計算された後、再び1つのオペランドとしてオペランドスタックにプッシュされます。 あなたの数式:a / b + f - (c + d)* e - a * c * **a** * オペランドスタックに`push` * **オペランド** :a * **演算子** : * **/** * 演算子スタックに`push` * **オペランド** :a * **演算子** :/ * **b** * オペランドスタックに`push` * **オペランド** :ab * **演算子** :/ * **+** * `+` <= `/` - > pop /、a **&** b - > a **/** b - >オペランドスタックへのプッシュ * オペレータスタックに`+`を押し込む * **オペランド** :(a / b) * **演算子** :+ * **f** * オペランドスタックにプッシュ * **オペランド** :(a / b)f * **演算子** :+ * **-** * `-` <= `+` - > pop +、(a / b) **&** f - >(a / b) **+** f - >オペランドスタックにプッシュ * **オペランド** :((a / b)+ f) * **演算子** : - * **(** * 演算子スタックにプッシュ * **オペランド** :((a / b)+ f) * **演算子** : - ( * **c** * オペランドスタックにプッシュ * **オペランド** :((a / b)+ f)c * **演算子** : - ( * **+** * 演算子スタックにプッシュ * **オペランド** :((a / b)+ f)c * **演算子** : - (+ * **d** * オペランドスタックにプッシュ * **オペランド** :((a / b)+ f)cd * **演算子** : - (+ * **)** * '('がポップされ、スタック内のすべての演算子を1つずつポップし、2つのオペランドで計算する * - >ポップ+、c **&** d - > c **+** d - >オペランドスタックにプッシュ * **オペランド** :((a / b)+ f)(c + d) * **演算子** : - ( * - > pop(、演算子スタックのポップを止める * **オペランド** :((a / b)+ f)(c + d) * **演算子** : - * * * `*` > `-`オペレータスタックにプッシュ * **オペランド** :((a / b)+ f)(c + d) * **演算子** : - * * **e** * `*` > `-`オペランドスタックにプッシュ * **オペランド** :((a / b)+ f)(c + d)e * **演算子** : - * * **-** * `-` <= `*` pop *、(c + d) **&** e - >(c + d)* e - >オペランドスタックにプッシュ * **オペランド** :((a / b)+ f)((c + d)* e) * **演算子** : - * `-` <= `-`ポップ- 、((/ B)+ **F)・((C** + D)* E) - >((/ B)+ F) **- ((C** + D)* E) - >プッシュオペランドスタックへ * プッシュツーオペレータスタック * **オペランド** :(((a / b)+ f) - ((c + d)* e)) * **演算子** : - * **a** * オペランドスタックにプッシュ * **オペランド** :(((a / b)+ f) - ((c + d)* e))a * **演算子** : - * * * `*` > `-`オペレータスタックにプッシュ * **オペランド** :(((a / b)+ f) - ((c + d)* e))a * **演算子** : - * * c * オペランドスタックにプッシュ * **オペランド** :(((a / b)+ f) - ((c + d)* e))ac * **演算子** : - * * **行末** * スタック内のすべての演算子を1つずつポップする * pop *、a&c - >(a * c) - >オペランドスタックへのプッシュ * **オペランド** :(((a / b)+ f) - ((c + d)* e))(a * c) * **演算子** : - * ポップ- 、(((/ B)+ F) - ((C + D)* **E))&(*** c)は- >(((/ B)+ F) - ((C + D)* e)) **-** (a * c) - >オペランドスタックへのプッシュ * **オペランド** :((((a / b)+ f) - ((c + d)* e)) - (a * c)) * **演算子** : 結果:((((a / b)+ f) - ((c + d)* e)) - (a * c))