Expression Tree功能异常求助：计算结果与树打印不符合预期

输入表达式(3+10)*(5)时，程序计算结果应为65却输出0，打印树结构显示* 5 ( ，完全不符合预期。以下是问题原因分析及修复方案：

核心错误点 #

1. 括号处理逻辑完全错误 #

遇到右括号)时，当前代码错误地将栈顶的右操作数当作运算符弹出，且未丢弃左括号(，导致树结构彻底混乱。正确的栈顺序应为：( → 左操作数 → 运算符 → 右操作数，遇到)时需依次弹出右操作数、运算符、左操作数，最后弹出并丢弃(，再将运算符节点挂载左右子树后压入栈。

2. 多位数存储方式错误 #

处理多位数时，代码将整数转为(char)(value + '0')，仅对0-9的个位数有效。比如数字10会被转为ASCII码58对应的字符:，虽巧合下计算结果正确，但属于错误实现，无法处理大于9的数字。

3. 树遍历顺序错误 #

当前打印逻辑采用逆中序遍历（右→根→左），导致输出混乱，无法正确还原表达式结构。

修复方案 #

1. 修正括号处理逻辑 #

修改)分支的代码，调整弹出顺序并丢弃左括号：

else if (character == ')') {
    ExpressionNode rightNode = stack.pop();
    ExpressionNode operator = stack.pop();
    ExpressionNode leftNode = stack.pop();
    stack.pop(); // 弹出并丢弃左括号'('
    operator.left = leftNode;
    operator.right = rightNode;
    stack.push(operator);
}

2. 重构节点结构以支持多位数 #

重新定义ExpressionNode，区分数字节点和运算符节点：

private static class ExpressionNode {
    char op;
    int value;
    boolean isNumber;
    ExpressionNode left;
    ExpressionNode right;

    // 运算符节点构造器
    public ExpressionNode(char op) {
        this.op = op;
        this.isNumber = false;
        this.left = null;
        this.right = null;
    }

    // 数字节点构造器
    public ExpressionNode(int value) {
        this.value = value;
        this.isNumber = true;
        this.left = null;
        this.right = null;
    }
}

同时修改数字入栈逻辑，直接创建数字节点：

else {
    StringBuilder number = new StringBuilder();
    while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
        number.append(expression.charAt(i));
        i++;
    }
    i--;

    int value = Integer.parseInt(number.toString());
    stack.push(new ExpressionNode(value));
}

3. 适配节点结构修改求值方法 #

更新evaluate方法，根据节点类型处理：

private int evaluate(ExpressionNode node) {
    if (node == null) {
        return 0;
    }

    if (node.isNumber) {
        return node.value;
    }

    int left = evaluate(node.left);
    int right = evaluate(node.right);

    return switch (node.op) {
        case '+' -> left + right;
        case '-' -> left - right;
        case '*' -> left * right;
        case '/' -> left / right;
        default -> 0;
    };
}

4. 修正树打印的遍历顺序 #

改为中序遍历，并给运算符节点添加括号，还原表达式结构：

private void recursivePrintTree(ExpressionNode node) {
    if (node == null) {
        return;
    }

    if (!node.isNumber) {
        System.out.print("(");
    }

    recursivePrintTree(node.left);
    System.out.print(node.isNumber ? node.value + " " : node.op + " ");
    recursivePrintTree(node.right);

    if (!node.isNumber) {
        System.out.print(") ");
    }
}

完整修复代码 #

package proyecto.pkg3;

import java.util.Stack;

public class ExpressionTree {
    private ExpressionNode root;

    private static class ExpressionNode {
        char op;
        int value;
        boolean isNumber;
        ExpressionNode left;
        ExpressionNode right;

        public ExpressionNode(char op) {
            this.op = op;
            this.isNumber = false;
            this.left = null;
            this.right = null;
        }

        public ExpressionNode(int value) {
            this.value = value;
            this.isNumber = true;
            this.left = null;
            this.right = null;
        }
    }

    public ExpressionTree() {
        root = null;
    }

    public void buildTree(String expression) {
        Stack<ExpressionNode> stack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char character = expression.charAt(i);

            if (character == ' ') {
                continue;
            }

            if (character == '(') {
                stack.push(new ExpressionNode(character));
            } else if (character == ')') {
                ExpressionNode rightNode = stack.pop();
                ExpressionNode operator = stack.pop();
                ExpressionNode leftNode = stack.pop();
                stack.pop(); // 弹出左括号
                operator.left = leftNode;
                operator.right = rightNode;
                stack.push(operator);
            } else if (isOperator(character)) {
                stack.push(new ExpressionNode(character));
            } else {
                StringBuilder number = new StringBuilder();
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    number.append(expression.charAt(i));
                    i++;
                }
                i--;

                int value = Integer.parseInt(number.toString());
                stack.push(new ExpressionNode(value));
            }
        }

        root = stack.isEmpty() ? null : stack.pop();
    }

    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    private int evaluate(ExpressionNode node) {
        if (node == null) {
            return 0;
        }

        if (node.isNumber) {
            return node.value;
        }

        int left = evaluate(node.left);
        int right = evaluate(node.right);

        return switch (node.op) {
            case '+' -> left + right;
            case '-' -> left - right;
            case '*' -> left * right;
            case '/' -> left / right;
            default -> 0;
        };
    }

    public void printTree() {
        recursivePrintTree(root);
    }

    private void recursivePrintTree(ExpressionNode node) {
        if (node == null) {
            return;
        }

        if (!node.isNumber) {
            System.out.print("(");
        }

        recursivePrintTree(node.left);
        System.out.print(node.isNumber ? node.value + " " : node.op + " ");
        recursivePrintTree(node.right);

        if (!node.isNumber) {
            System.out.print(") ");
        }
    }

    public int solve() {
        return evaluate(root);
    }
}

验证结果 #

输入(3+10)*(5)，调用solve()返回65，调用printTree()输出((3 + 10 ) * 5 ) ，完全符合预期。

内容的提问来源于stack exchange，提问作者Alex_Vargas