c - 从堆栈递归构建二叉表达式树背后的逻辑

Question

我正在构建使用运算符、变量和整数的二元表达式树。

用户输入表达式，我们根据空格对其进行标记，并将每个标记放入堆栈中。

例如，

用户输入:a b +

我们的堆栈变成 Stack = ["+", "b", "a"]

我有一个创建表达式节点的函数。

xpNode* createExpressionNode(char token[], xpNode *left, xpNode *right)

这就是我努力掌握递归概念的地方，这是我想出的伪代码来帮助我理解它应该如何工作。如果有人可以看一下并阐明当堆栈为空时该怎么做，以及这里是否还有其他问题，我将不胜感激。

xpNode* createTree(Stack *stack){
{
   xpNode *node;
   get the top of the stack and store it in data
   pop the stack
   if the stack is empty, do something //im lost on what to do here
   if the top is an integer, node = createExpressionNode(data, NULL NULL) //the left and right arguments will always be NULL because integer's wont have any children
   if the top is a variable, node = createExpressionNode(data, NULL, NULL) //the left and right arguments will always be NULL because variables wont have any children
   if the top is an operator, node = createExpressionNode(data, createTree(stack), createTree(stack)) //Operators have children so we need to recursively get them

   return node
}

输入的结果:a b + 应该是一棵看起来像这样的树:

     +
    / \
   a   b 

Answer 1

这种表示的要点难道不是您不需要递归吗？逻辑应该是这样的

stack = an empty stack;
while (token = read_next_token()) {
  if (token is a term) {
    push(stack, createTerm(token));
  } else if (token is a unary operator) {
    push(stack, createUnOp(token, pop(stack)));
  } else if (token is a binary operator) {
    node *left, *right;
    left = pop(stack);
    right = pop(stack);
    push(stack, createBinOp(token, left, right));
  } else {
    error("unrecognized input");
  }
}

在输入结束时，堆栈上应该有一个元素，它是一棵代表整个表达式的树。如果堆栈末尾有多个元素，则输入格式错误。如果在任何时候您尝试在堆栈为空时弹出堆栈，则输入格式错误。