java - 从表达式树打印后序表达式时出现问题。 ( java )

Question

这是我的代码。但是，每当我输入“2*3+6/3”等表达式时，它都会将输出打印为“36/3+2*”，这不是正确的后缀格式。有人看到我的代码中有任何错误吗？非常感谢!

package expressiontree;
import java.util.LinkedList;
import java.util.List;

class Stack
{
    private List stack = new LinkedList();

    public void push(TreeNode node)
    {
        stack.add(node);
    }

    public TreeNode pop()
    {
        int top = stack.size()-1;
        if (top < 0) return null;
        TreeNode node = (TreeNode)stack.get(top);
        stack.remove(top);
        return node;
    }
}

class TreeNode
{
    TreeNode left;
    TreeNode right;
    char data;

    TreeNode(){}

    TreeNode(char c)
    {
        this.data = c;
    }
}

public class ExpressionTree {

    String expression;
    TreeNode tree;
    Stack operandstack = new Stack();
    Stack operatorstack = new Stack();

    private boolean isOperator(char c)
    {
        String operator = "+-*/";
        if(operator.indexOf(c)==-1)
        return false;

        return true;
    }

    // parses an expression and creates two stacks
    private void parseExpression(String exp)
    {
        for(int i=0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            if(isOperator(c))
            operatorstack.push(new TreeNode(c));
            else{
                operandstack.push(new TreeNode(c));
            }
        }
    }

    private TreeNode create_tree()
    {
        TreeNode node = new TreeNode();
        while((node = operatorstack.pop())!=null)
        {
            TreeNode oper1 = operandstack.pop();
            TreeNode oper2 = operandstack.pop();

            TreeNode exp = create_expression(oper1, node, oper2);
            operandstack.push(exp);
        }

        return operandstack.pop();
    }

    private TreeNode create_expression(TreeNode oper1, TreeNode operator, TreeNode oper2)
    {
        TreeNode expression = new TreeNode(operator.data);
        expression.left = oper1;
        expression.right = oper2;

        return expression;
    }

    public static void postfix(TreeNode tn){
        if (tn == null){
            return;
        }
        else{
            postfix(tn.left);
            postfix(tn.right);  
            System.out.print(tn.data);
        }
    }

    public static void main(String[] args)
    {
        ExpressionTree et = new ExpressionTree();
        String expression = "2*3+6/3";
        et.parseExpression(expression);
        TreeNode tn = et.create_tree();
        postfix(tn);
        System.out.println();
    }
}

Answer 1

我可以看到代码有两个基本问题。

1) 在parseExpression中，操作数和运算符被盲目地插入各自的堆栈中。您需要注意运算符优先级(即 * 和/的优先级高于 + -)。为了照顾运算符优先级，基本上，当您看到一个运算符的优先级低于或等于当前运算符堆栈中的运算符时，您必须先评估堆栈中当前的内容，然后再将该运算符插入堆栈。

2) 在create_tree中，从堆栈分配第一个和第二个操作数的代码使用第一个弹出操作数作为第一个操作数，使用第二个弹出操作数作为第二操作数。应该是相反的(即第一个弹出是第二个操作数，第二个弹出是第一个操作数)

尝试这些更改，看看是否可以解决您的问题。