将中缀表达式读入堆栈

Question

我已经编写了将表达式树转换为前序和后序的代码，但我正在努力从中缀表达式实际构建表达式树。我有一个 .cc 文件，它将调用 build_expression_tree 函数，调用转换函数并打印出转换后的表达式。

这是我当前的非工作函数：

void Expression_Tree::build_expression_tree(char input[], int size)
{
    for (int i = 0; i < size; i++) 
    {
        if (input[i] == ' ')
        {
            i++;
        }
        if(input[i] >= '0' && input[i] <= 9) 
        { 
            ETNode *temp = new ETNode;
            temp->left = temp->right = NULL;
            temp->input = input[i];

            tree_stack.push(temp);
        }
        else if (input[i] == '(') 
        {
            ETNode *temp = new ETNode;
            temp->left = temp->right = NULL;
            temp->input = input[i];

            tree_stack.push(temp);
        }
        else if (input[i] == ')')
        {
            while (tree_stack.top() != '(')
            {
                temp->right = tree_stack.top();
                tree_stack.pop();
                temp->left = tree_stack.top();
                tree_stack.pop();
                tree_stack.pop();
                tree_stack.push(temp);
            }
        }
        else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
        {
            while (!tree_stack.empty())
            {
                ETNode *temp = new ETNode;
                temp->left = temp->right = NULL;
                temp->input = input[i];

                tree_stack.push(temp);

                temp->right = tree_stack.top();
                tree_stack.pop();
                temp->left = tree_stack.top();
                tree_stack.pop();

                tree_stack.push(temp);
            }
        }
    }
}

此时我遇到的错误是： Expression_Tree.h:61:40: 错误：ISO C++ 禁止比较指针和整数

while(tree_stack.top() != '(')

Expression_Tree.h:62:13: 错误: 'temp' 未在此范围内声明

temp->right = tree_stack.top();

Expression_Tree.h:62:13: 错误: 'temp' 未在此范围内声明

temp->left = tree_stack.top();

我知道为什么会出现最后两个错误（未在范围内声明），但我只是不知道如何在使我的代码正常工作的同时修复它。

我什至不知道我的代码是否完全错误，但如果有任何提示，我将不胜感激！谢谢。

编辑：这些是影响 Build_Expression_Tree 功能的类。

class ETNode {
public:
    char input;
    ETNode *left, *right;
};

class Expression_Tree { 
public:
    Expression_Tree() { root = 0; };
    ~Expression_Tree() { clear(root); }
    void build_expression_tree(char[], int);
    void inorder() { inorder(root); }
    void preorder() { preorder(root); }
    void postorder() {postorder(root); }
private:
    ETNode* root;
    std::stack<ETNode*> tree_stack;
    void visit(ETNode* p) { std::cout << p->input << " "; } 
    void inorder(ETNode*);
    void preorder(ETNode*);
    void postorder(ETNode*);
    void clear(ETNode*);
};

Answer 1

快速浏览一下就会发现您需要 ETNode *temp = new ETNode; 就在 while(tree_stack.top() != '(') 之后。不过我没有检查逻辑。

Answer 2

在这里，我将您的示例输入拆分为如何使用堆栈的表示以及在每个输入上做出的决定。

//    _ = nullptr or empty
//    # = pointer to subtree (not just a number)
// | ___ |     |     |     begin (empty element on stack)
// | 2__ |     |     |  2  make number node and set to top->left if empty, else top->right
// | 2+_ |     |     |  +  set top->input if not set, else pop parent into left of new node
// | 2+_ | ___ |     |  (  make new node on stack
// | 2+_ | 3__ |     |  3  make number node and set to top->left if empty, else top->right
// | 2+_ | 3*_ |     |  *  set top->input if not set, else pop parent into left of new node
// | 2+_ | 3*_ | ___ |  (  make new node on stack
// | 2+_ | 3*_ | 2__ |  2  make number node and set to top->left if empty, else top->right
// | 2+_ | 3*_ | 2+_ |  +  set top->input if not set, else pop parent into left of new node
// | 2+_ | 3*_ | 2+2 |  2  make number node and set to top->left if empty, else top->right
// | 2+_ | 3*# |     |  )  pop it off into its parent
// | 2+# |     |     |  )  pop it off into its parent
// | #+_ |     |     |  +  set top->input if not set, else pop parent into left of new node
// | #+5 |     |     |  5  make number node and set to top->left if empty, else top->right

请注意，我有很多重复的语句，一种用于 ( 一种用于 ) 一种用于数字 0-9 一种用于每个操作 +-*/。您的代码中已经有了这些部门，所以您走在正确的轨道上。

(的唯一工作应该是在栈顶创建一个新节点。在您的代码中，没有必要设置 input = '(' 因为它稍后会被实际输入覆盖，并且它在堆栈中的位置就是跟踪它所需要的。您应该将 input 初始化为 '[=19=]' 或其他意思为空的东西。

) 的工作应该是从堆栈中弹出顶部并将其放在需要去的地方。如果它为 null，那将是下一个顶部的左节点，否则它将是顶部的右节点。你不需要像你一样向下循环堆栈，因为它总是只是我们感兴趣的弹出的顶部。

数字的工作应该是将自己创建为一个新的节点，并将自己放在需要去的地方。就像 ) 一样，如果它为空，它要么是顶部的左节点，否则它将是顶部的右节点。在您的代码中，您创建了节点，但您没有将它放在堆栈之外的任何地方。它在那里没有任何好处，因为数字节点将始终是叶节点（没有右或左）。

最后一个操作的工作应该是简单地将自己设置为顶部的 input。但是，有一种特殊情况，顶部已经被填充（当您执行 1+2+3 时，1+2 是顶部的节点）。所以在这种情况下你可以做的是从顶部弹出，将一个新节点推到顶部，将旧顶部添加到左侧，然后将其自身设置为顶部的 input。你不需要循环。

全部完成后，您可以设置root = tree_stack.top()。

如果你想要代码，我可以提供，但我希望我的解释足够了。

代码：这似乎对我有用

void Expression_Tree::build_expression_tree(char input[], int size)
{
  // assuming empty tree_stack, it shouldn't really be a member 
  // variable since its only used for building
  //std::stack<ETNode*> tree_stack;

  // make empty node, should really make a default constructor set all this up
  tree_stack.push(new ETNode);
  tree_stack.top()->left  = nullptr;
  tree_stack.top()->right = nullptr;
  tree_stack.top()->input = '[=11=]';

  for (int i = 0; i < size; i++)
  {
    if (input[i] == ' ')
    {
      i++;
    }
    if (input[i] >= '0' && input[i] <= '9') // this 9 had a typo before
    {
      // create number leaf
      ETNode *temp = new ETNode;
      temp->left = nullptr;
      temp->right = nullptr; 
      temp->input = input[i];

      // put where it needs to go
      if (tree_stack.top()->left == nullptr)
        tree_stack.top()->left = temp;
      else
        tree_stack.top()->right = temp;
    }
    else if (input[i] == '(')
    {
      // make empty node
      ETNode *temp = new ETNode;
      temp->left = nullptr;
      temp->right = nullptr;
      temp->input = '[=11=]';

      tree_stack.push(temp);
    }
    else if (input[i] == ')')
    {
      // pop top from the stack
      ETNode *temp = tree_stack.top();
      tree_stack.pop();

      // put where it needs to go
      if (tree_stack.top()->left == nullptr)
        tree_stack.top()->left = temp;
      else
        tree_stack.top()->right = temp;
    }
    else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
    {
      // shuffle node if already filled
      if (tree_stack.top()->input != '[=11=]')
      {
        ETNode *old = tree_stack.top();
        tree_stack.pop();

        ETNode *temp = new ETNode;
        temp->left = old;
        temp->right = nullptr;

        tree_stack.push(temp);
      }

      tree_stack.top()->input = input[i];
    }
  }

  // set root node
  root = tree_stack.top();
}

将中缀表达式读入堆栈

Read infix expression into a stack

c++

stack

expression-trees

infix-notation