计算二叉树中的表达式 Java

Question

我创建了一个表达式的二叉树，并将运算符（+、-、/、*）作为根，将操作数（值）作为子节点 left/right。我需要使用参数 (T, v) 在二叉树中评估该表达式，其中 'T' 是二叉树，'v' 是后序遍历开始的节点。

我搜索了后序遍历的工作原理以及我所理解的所有内容。但是我不知道如何使用节点 'v' 来实现后序遍历的代码。

我的方法是这样的...

public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) {

}

这应该 return 运算符正在其运算符（根的子级）上使用。所以，我明白该怎么做，我被困在如何实际去做上。 -.-

Answer 1

您不需要提供整棵树，也不需要单独的 Position class。每个子树都是一棵树。你只需要这样的东西：

public class <T extends Number> ExpressionTree<T> {
    private ExpressionTree<T> left, right;
    private T value;
    private int operator;

    // constructors, getters, setters, etc. elided

    public T evaluateExpression() {
        // Here I am assuming a <T> value field that is set if the node
        // is a literal value rather than an expression subtree with left and right children.
        if (this.value != null)
            return this.value;
        // Evaluate the subtree
        switch (this.operator) {
        case '+':
            return left.evaluateExpression()+right.evaluateExpression();
        // etc for the other operators
        }
    }

您不应该使用下面评论中提到的 LinkedBinaryTree class。它无论如何都不是为此目的而设计的，在我看来，即使是为了它自己的目的，它也显得不必要地复杂。

Answer 2

通常，在现实世界中，您会按照 EJP 的建议进行操作。

就是说，后序迭代器会以正确的顺序为您提供存储在树中的值和运算符，基本上可以做到这一点：

如果元素是数字，将其压入数字堆栈
如果元素是运算，则从数栈中弹出两个元素，按运算处理并压入结果

遍历后，return栈上唯一的元素

计算二叉树中的表达式 Java

Evaluating an Expression in a Binary Tree Java

java

algorithm

binary-tree