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

// 假设的Node类定义
class Node {
    String exp; // 存储操作数或操作符
    Node left;  // 左子节点
    Node right; // 右子节点

    // 构造函数用于叶节点（操作数）
    public Node(String exp) {
        this.exp = exp;
        this.left = null;
        this.right = null;
    }

    // 构造函数用于内部节点（操作符）
    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 class PostfixConverter {

    /**
     * 将解析树转换为后缀表达式字符串。
     * 使用后序遍历算法。
     *
     * @param root 解析树的根节点。
     * @return 对应的后缀表达式字符串。
     */
    public String convertToPostfix(Node root) {
        if (root == null) {
            return ""; // 空树返回空字符串
        }

        StringBuilder result = new StringBuilder();

        // 1. 递归处理左子树
        result.append(convertToPostfix(root.getLeft()));
        // 2. 递归处理右子树
        result.append(convertToPostfix(root.getRight()));
        // 3. 处理当前节点（操作符或操作数）
        result.append(root.getExp());

        return result.toString();
    }

    // 示例用法
    public static void main(String[] args) {
        PostfixConverter converter = new PostfixConverter();

        // 示例1: 正确的解析树，对应中缀表达式 3 + (4 * 2) + 8
        // 预期后缀表达式: 342*+8+
        Node node4 = new Node("4");
        Node node2 = new Node("2");
        Node nodeMul = new Node("*", node4, node2); // 4 * 2
        Node node3 = new Node("3");
        Node nodePlus1 = new Node("+", node3, nodeMul); // 3 + (4 * 2)
        Node node8 = new Node("8");
        Node rootCorrect = new Node("+", nodePlus1, node8); // (3 + (4 * 2)) + 8

        System.out.println("正确解析树生成的后缀表达式: " + converter.convertToPostfix(rootCorrect)); // 输出: 342*+8+

        // 示例2: 错误的解析树，对应中缀表达式 (3 + 4) * 2 + 8
        // 预期后缀表达式: 34+2*8+ (与实际问题中的错误输出一致)
        Node node3_err = new Node("3");
        Node node4_err = new Node("4");
        Node nodePlus_err = new Node("+", node3_err, node4_err); // 3 + 4
        Node node2_err = new Node("2");
        Node nodeMul_err = new Node("*", nodePlus_err, node2_err); // (3 + 4) * 2
        Node node8_err = new Node("8");
        Node rootIncorrect = new Node("+", nodeMul_err, node8_err); // ((3 + 4) * 2) + 8

        System.out.println("错误解析树生成的后缀表达式: " + converter.convertToPostfix(rootIncorrect)); // 输出: 34+2*8+
    }
}