c++ - 如何为算术表达式创建 BST

Question

我是一个 c++ 学习者，我正在尝试为此表达式创建一个 BST 树:2346*+/8+，并执行中序和后序以获得表达式的修复版本和后修复版本。我很难为表达式创建二叉树。这是我的比索代码:

Tree:
Stack:
inorder fn{}
postorder fn{}
main{
  input the file;
    while(expression){
      if(digit){
         s.push}
      else if(operator){
         s.top = right;
         s.pop;
         s.top = left;
         s.pop;
         T1 = new Tree(operator, left, right);
     }
    }

我要创建的树是这样的

           +
          / \
        (/)  8
        / \
       +   2  
      / \
     *   3
    / \
   4   6

此代码的问题是在创建 (4*6) 树之后，我无法将 (+3) 链接到 (4*6)。请帮助我。

感谢 Drew McGowen，我更新了我的代码，现在我将 4*6 树推回堆栈，这是代码:

while(input_file >> expression){
    if(isdigit(expression[0])){
        sscanf(expression,"%c",&digit);
        printf("reading a number: %c \n",digit);
        Tree* s.push(digit);
    }
    else {
        sscanf(expression,"%c",&oper);
        printf("reading an operator: %c \n",oper);
        T1 = new Tree(s.top(), NULL, NULL);
        s.pop();
        T2 = new Tree(s.top(), NULL, NULL);
        s.pop;
        myTree = new Tree(oper, T1, T2);
        s.push(myTree);

我不断收到错误消息，有人可以帮我检查一下代码吗？谢谢大家。

大家好，我认为主要部分是在正确的轨道上，但我应该如何修改堆栈函数以接受树？这是我的堆栈函数:

void Stack::Push(char newthing) {
index++;
data[index] = newthing;
}
  void Stack::Pop() {
  if (index > -1) { index--; }
 }
 char Stack::Top() {
 return data[index];

Answer 1

您的堆栈似乎包含数字。为了将后缀表示法中的表达式解析为堆栈，堆栈应包含树元素。

伪代码:

main{
  input the file;
    while(expression){
      if(digit){
         s.push(new Tree(digit)); //create leaf-element
      }
      else if(operator){
         Tree tr = s.pop();
         Tree tl = s.pop();
         T1 = new Tree(operator,tl,tr);
     }
}

这或多或少也是 L(AL)R 解析器的工作方式。

关于您的代码:

• 您应该将顺序颠倒到T2 和T1，因为您是从堆栈中弹出；
• T1 和T2 应该是简单的弹出操作，没有构造函数调用；和

• 你应该构建一个数字大小写的树节点(叶子)。

  while(input_file >> expression){
      if(isdigit(expression[0])){
          sscanf(expression,"%c",&digit);
          printf("reading a number: %c \n",digit);
          s.push(new Tree(digit,NULL,NULL)); //create new leaf
      }
      else {
          sscanf(expression,"%c",&oper);
          printf("reading an operator: %c \n",oper);
          T2 = s.top(); //T2 instead of T1 and simple pop
          s.pop();
          T1 = s.top(); //T1 instead of T2 and simple pop
          s.pop;
          myTree = new Tree(oper, T1, T2);
          s.push(myTree);
      }
  }
  

如果输入流是有效的(例如不是 1+ 或 12+6)，结果是一个包含一个元素的堆栈:表达式树。