C++分流碼算法和表達樹實現

Question

我是C++新手，使用分流碼算法來構建表達式樹。我一直在困擾這個問題幾天。我正在嘗試獲取根節點的值，但失敗。

---

綴輸入

(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函數中。構建完成後，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表示法構建節點後，您的堆棧中應該只剩下一個節點。返回該節點或以該節點爲根的樹。

因此，基本上：

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

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

return ExprTree(stack.top()); 

您還可以跟蹤頂部，當您去，但如果你這樣做，你必須使新運營商的節點上。在你的代碼中，你將右手操作數放在最上面。

請注意，在這種情況下，您應該在處理數字時跟蹤頂部，否則當表達式只包含一個數字時，您將有一個空頂部節點。另外請注意，如果你做得正確，yourtop將始終是最後一個項目，也就是堆棧的頂部，推入堆棧–。