递归在java中创建给定前缀符号的二进制表达式树

Question

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

（*/8+514+3-5/186） 四,

伪代码是这样的：

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，太乱了

Answer 1

更多伪代码：

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), "*")

注意，这些前缀表达式看不出“-”是一元求反还是二元减法。因此，不能使用相同的运算符字符

Answer 2

请看这里的最后两个答案

parsing math expression in c/c++

我认为它们很有用

您需要一个形式语法，然后是一个递归下降解析器。 不确定您是否完全熟悉这两个概念。 如果没有，你应该多读一些关于他们的书