我们应该如何构造以下“前缀”顺序表达式的二进制树?

(-* / 8 + 5 1 4 + 3-5 / 18 6)
4

伪代码是这样的:

public ExpressionRootNode MakeBinaryTree(expr):
    element = next element in expr
    if element is a number:
        return a leaf node of that number
    else: // element is an operator
        left = MakeBinaryTree(expr)
        right = MakeBinaryTree(expr)
        return a binary tree with subtrees left and right and with operator element
        //^aka return root


但是,我不太了解如何递归调用该函数来创建所述树。
我尝试查看如何Create a binary tree from an algebraic expression,但无法弄清楚如何回溯到另一个节点。

项目文件:http://pastebin.com/BJiPtDM5,一团糟。

最佳答案

更多伪代码:

abstract class Tree { .... }
class Leave extends Tree { int number; ... }
class Expr  extends Tree { Tree left, right; String operation;  .... }

public Tree makeBinaryTree(expr):
   element = next element in expr
   if element is a number:
      return new Leave(element)
   else: // element is an operator
      left = makeBinaryTree(expr)
      right = makeBinaryTree(expr)
   return new Expr(left, right, element)


Leave / Expr的构造函数应仅根据其参数设置字段。

不过,剩下要做的是一些错误处理。哦,请确保“ expr中的下一个元素”也删除了已经处理过的部分。

给定正确的输入,它将像这样工作:


如果输入只是一个数字,它将返回带有该数字的请假
如果输入的格式为OP L R,它将记住OP,从L生成左子树,从R生成右子树,并将其作为表达式返回。
没有其他输入可能/有效


例:

* + 5 1 7


将导致:

Expr(Expr(Leave(5), Leave(1), "+"), Leave(7), "*")


请注意,这些前缀表达式无法查看“-”是否应为一元否定或二进制减法。因此,您不能为此使用相同的运算符。

09-25 22:05
查看更多