java - 计算器算法 - 在二叉搜索树上使用迭代而不是递归

Question

除了我正在计算计算器的表达式输入之外，我已经看到了如何遍历二叉树并找到所有节点的总和的方法。节点根据操作顺序以适当的顺序排列，节点是operators或operands。我认为 recursion 比迭代慢，所以我想弄清楚如何遍历二叉树并找到在没有 recursion 的情况下输入的表达式的结果。

树的例子:

      +
  *       /
3   4   4   2

我到目前为止的递归方法(我为运算符使用了一个枚举):

public static float evaluate(BETNode root)
{
    if (root == null)
    {
        throw new IllegalArgumentException("Error: Root is null!");
    }

    if (root.getType() == BETNodeType.OPERAND)
    {
        return root.getOperand();
    }

    float leftValue = evaluate(root.getLeft());
    float rightValue = evaluate(root.getRight());

    switch (root.getOperator())
    {
        case '+':
            return leftValue + rightValue;

        case '-':
            return leftValue - rightValue;

        case '*':
            return leftValue * rightValue;

        case '/':
            return leftValue/rightValue;
    }

    throw new IllegalArgumentException("Error.");
}

Answer 1

正如我在上面的评论中提到的，如果你做了 iterative post-order traversal ，您将按以下顺序获得节点:

3, 4, *, 4, 2,/, +。

由此，您只需要一个堆栈来计算表达式。

Push 3
Push 4
Push (pop() * pop())

Push 4
Push 2
Push (pop() / pop())
Push (pop() + pop())
//Result

同样有趣的是 Shunting Yard Algorithm它根据中缀表达式进行求值。