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将始终是最后一个项目，也就是堆栈的顶部，推入堆栈–。