从解析树生成后缀表达式：原理、实现与常见陷阱

public class Node {
    private String exp; // 节点存储的表达式部分，可以是操作数或操作符
    private Node left;  // 左子节点
    private Node right; // 右子节点

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

    public Node(String exp, Node left, Node right) {
        this.exp = exp;
        this.left = left;
        this.right = right;
    }

    public String getExp() {
        return exp;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    // 辅助方法：从解析树生成后缀表达式字符串
    public static String toPostfixString(Node root) {
        StringBuilder result = new StringBuilder();
        if (root == null) {
            return "";
        }

        // 1. 递归遍历左子树
        result.append(toPostfixString(root.getLeft()));
        // 2. 递归遍历右子树
        result.append(toPostfixString(root.getRight()));
        // 3. 访问根节点
        result.append(root.getExp());

        return result.toString();
    }

    public static void main(String[] args) {
        // 示例：构建一个正确的解析树 for 3+4*2+8
        // 期望的后缀表达式：3 4 2 * + 8 +
        // 对应解析树结构：
        //       +
        //      / \
        //     +   8
        //    / \
        //   3   *
        //      / \
        //     4   2

        Node node4 = new Node("4");
        Node node2 = new Node("2");
        Node multiply = new Node("*", node4, node2); // 4 * 2

        Node node3 = new Node("3");
        Node plus1 = new Node("+", node3, multiply); // 3 + (4 * 2)

        Node node8 = new Node("8");
        Node plus2 = new Node("+", plus1, node8); // (3 + (4 * 2)) + 8

        System.out.println("正确解析树的后缀表达式: " + toPostfixString(plus2)); // 预期输出: 342*+8+

        // 示例：构建一个错误的解析树 for ((3+4)*2+8)
        // 期望的后缀表达式：3 4 + 2 * 8 +
        // 对应解析树结构：
        //       +
        //      / \
        //     *   8
        //    / \
        //   +   2
        //  / \
        // 3   4

        Node node3_err = new Node("3");
        Node node4_err = new Node("4");
        Node plus_err = new Node("+", node3_err, node4_err); // 3 + 4

        Node node2_err = new Node("2");
        Node multiply_err = new Node("*", plus_err, node2_err); // (3 + 4) * 2

        Node node8_err = new Node("8");
        Node plus2_err = new Node("+", multiply_err, node8_err); // ((3 + 4) * 2) + 8

        System.out.println("错误解析树的后缀表达式: " + toPostfixString(plus2_err)); // 预期输出: 34+2*8+
    }
}