Java递归实现Prefix前缀表达式转Postfix后缀表达式异常排查

核心问题排查 #

• 递归终止逻辑错误：当前代码遇到长度为1的子串时返回null，没有正确返回操作数字符，同时缺少操作数的直接返回分支
• 子串重复处理：两次递归调用都传入了完整的剩余字符串，没有记录左操作数处理后消耗的字符长度，导致右操作数从子串开头重复处理，输出大量重复字符
• 拼接规则错误：后缀表达式的拼接规则应为左操作数后缀 + 右操作数后缀 + 当前运算符，现有代码错误拼接了剩余全部字符串

修正后实现代码 #

public static boolean operator(char o) {
    return o == '+' || o == '-' || o == '*' || o == '/' || o == '$';
}

// 入口方法
public static String preToPost(String s) {
    // 用长度为1的int数组传递下标，解决Java值传递无法修改基础类型的问题
    return preToPostHelper(s, new int[]{0});
}

// 递归辅助方法
private static String preToPostHelper(String s, int[] curIndex) {
    char currentChar = s.charAt(curIndex[0]);
    curIndex[0]++; // 下标后移，标记当前字符已处理
    
    // 操作数直接返回
    if (!operator(currentChar)) {
        return String.valueOf(currentChar);
    }
    
    // 运算符先递归取左右操作数的后缀形式
    String leftPost = preToPostHelper(s, curIndex);
    String rightPost = preToPostHelper(s, curIndex);
    
    // 按后缀规则拼接返回
    return leftPost + rightPost + currentChar;
}

验证说明 #

输入示例-+ABC调用preToPost方法，返回结果为AB+C-，完全符合预期。

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