java - 在 Java 中使用树计算 Postfix 表达式

Question

我应该使用表达式树来评估后缀表达式。 编译程序时出错

"The method getElement() is undefined for the type ExpressionTree.Node"

getElement 不适用于堆栈类吗？ 如果不是，我应该使用什么来获取堆栈中的元素？

import java.util.Stack;
public class ExpressionTree 
{
    Node root;

    // Node sub-class
    public class Node 
    {
        private String key; // key
        private Node left; // links to subtrees
        private Node right;

        public Node(String key)
        {
            this.key = key;
        }
    }

    // constructor to build a tree with postFix expression
    public ExpressionTree(String postFixExpression)
    {
        Stack<Node> stack = new Stack<Node>();
        String[] tokens = postFixExpression.split(" ");
        for (String token: tokens) 
        {
            if (isOperator(token))
            {
                Node right = stack.pop();
                Node left = stack.pop();
                Node node = new Node(token);
                node.left = left;
                node.right = right;
                stack.push(node);
            }
            else
            {
                stack.push(new Node(token));
            }
        }
        root = stack.pop();
    }

    private boolean isOperator(String token)
    {
        boolean result = false;
        switch(token) 
        {
            case "+":
            case "-":
            case "*":
            case "/":
                result = true;
                break;
            default:
                result = false;
        }
        return result;
    }

    /**
     * @return result of the expression
     * @throws Exception
     */
    public double evaluate() throws Exception
    {
        if (root==null)
            result = 0;
        else
        {
            temp = (ExpressionTreeOp)root.getElement();

            if (temp.isOperator())
            {
                operand1 = evaluateNode(root.getLeft());
                operand2 = evaluateNode(root.getRight());
                if (operator == '+')
            result = operand1 + operand2;

        else if (operator == '-')
            result = operand1 - operand2;
        else if (operator == '*')
            result = operand1 * operand2;
        else 
            result = operand1 / operand2;
            }
            else
                result = temp.getValue();
        }

        return result;

    }

}

Answer 1

root.getElement();

root 这里是 Node 类的对象。发生编译错误是因为此类没有名为 getElement 的方法:

// Node sub-class
public class Node 
{
    private String key; // key
    private Node left; // links to subtrees
    private Node right;

    public Node(String key)
    {
        this.key = key;
    }
}

Does getElement doesn't work for stack class?

您的示例代码中没有 stack 类。需要明确的是，Java 不会自动创建方法，您需要从某个现有类继承方法或自己实现它。

If not what should I use to get the elements in the stack?

我想你必须自己实现这个方法。

Node getElement() {
    //something
}

或者使用实际的Stack某处实现。该接口(interface)提供peek和pop方法来访问堆栈的头元素。