0

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

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

例如，

用户输入：ab +

我们的栈变成了 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
}

输入的结果：ab + 应该是一棵看起来像这样的树：

     +
    / \
   a   b
4

2 回答 2

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");
  }
}

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

于 2013-11-10T22:15:55.597 回答
0

如果那里的堆栈为空，则输入格式有误。例如，如果堆栈是[+ * 2 3]，则无法构建树 - 需要多一个值。

于 2013-11-10T22:01:20.707 回答