C++ shunting yardアルゴリズムと式ツリーの実装

Question

私はC++を初めて使用し、shunting yard algoを使用して式ツリーを構築しました。私は数日間この問題に悩まされています。ルートノードの値を取得しようとしていますが、失敗します。

---

中置入力

(1+2)*(3/4)-(5+6) 

次のコードは、庭をshungtingに基づく関数である：

vector<string> infixToRPN(vector<string> tokens) { 
    vector<string> output; 
    stack<string> stack; 
    string o1; 
    string o2; 
    //traverse tokens 
    for (int i = 0; i < tokens.size(); ++i) { 

     // if token is operator 
     if (isOperator(tokens[i])) { 
      string o1 = tokens[i]; 
      if (!stack.empty()) { 
       string o2 = stack.top(); 
       while (isOperator(o2) && comparePrecendence(o1, o2) <= 0) { 
        // pop off o2 and on to the output; 
        stack.pop(); 
        output.push_back(o2); 
        if (!stack.empty()) 
         o2 = stack.top(); 
        else 
         break; 
       } 

      } 
      //push o1 on to the stack; 
      stack.push(o1); 

     } 
     //if token is left bracket 
     else if (tokens[i] == "(") { 
      stack.push(tokens[i]); 
     } 
     //if token is right bracket 
     else if (tokens[i] == ")") { 
      string topToken = stack.top(); 
      while (stack.top() != "(") { 
       output.push_back(topToken); 
       stack.pop(); 
       if (stack.empty()) break; 
       topToken = stack.top(); 
      } 
      if (!stack.empty()) stack.pop(); 

     } 
     // if token is number and add it to ouput; 
     else 
     { 
      output.push_back(tokens[i]); 
     } 
    } 
    //pop the rest of token 
    while (!stack.empty()) { 
     string restToken = stack.top(); 
     output.push_back(restToken); 
     stack.pop(); 
    } 
    return output; 
} 

テスト結果は、パーサが働いているようだことを示唆している：

12+34/*56+- 

だから私は私のbuildTree関数でエラーが発生することがあります。 buiildingの後、getRoot（）関数によって返される値は、常に正しい値と矛盾します。私の場合、根は " - "でなければならず、私は "0"を得ました。

ExprTree ExprTree::buildTree(vector<string> tokens){ 
    ExprTree t ; 
    TreeNode * n, * n1, * n2; 
    TreeNode * r = t.getRoot(); 
    vector<string> postfix = infixToRPN(tokens); 
    stack<TreeNode *> stack; 
    for (int i = 0; i < postfix.size(); ++i) { 
     //if number 


     if (!isOperator(postfix[i])) { 
      n = createOperatorNode(postfix[i]); 
      stack.push(n); 
     } 
     else // if operator 
     { 
      n= createOperatorNode(postfix[i]); 
      if (!stack.empty()) 
       t = ExprTree(stack.top()); 
      // pop two tree nodes 
      n1 = stack.top(); 
      stack.pop(); 
      n2 = stack.top(); 
      stack.pop(); 
      //set children nodes; 
      n->setLeftChild(n2); 
      n->setRightChild(n1); 

      stack.push(n); 

     } 

    } 

    return t; 
} 

Answer 1

あなたのアルゴリズムはよく見えますが、返すツリーにはエラーがあります。

RPN表記法でノードを作成した後は、スタック内にノードが1つだけ残っている必要があります。そのノードまたはルートがそのノードであるツリーを返します。

だから、基本的には：あなたが行くように

for (int i = 0; i < postfix.size(); ++i) { 
    // build tree 
} 

// enforce that there is only one node on the stack 

return ExprTree(stack.top()); 

また、トップを追跡することができますが、あなたがそうするならば、あなたは、new演算子ノードトップにする必要があります。あなたのコードでは、右手オペランドを一番上にします。

この場合、数字を扱うときにもトップを記録する必要があります。そうしないと、式が数字のみで構成される場合にトップノードがヌルになります。また、正しく実行すると、yourtopは常にスタックにプッシュされた最後のアイテムになることに注意してください。–つまり、スタックの先頭です。