递归函数处理前缀转后缀表达式时index变量返回异常问题排查

问题根源 #

Java 中基本数据类型为值传递，你将int类型的index作为递归函数入参传递时，每层递归拿到的都是index的副本，子递归内部对index的修改只会作用在当前层的副本上，不会同步到上层调用方。你虽然定义了Storage类，但没有统一用它维护全递归链路的下标状态，才会出现子递归返回前index值正确、回到上层就变回旧值的问题。

最优修复方案 #

彻底取消将int index作为递归函数的独立入参，所有对下标的读取、修改操作全部统一操作Storage对象中的index成员：对象为引用传递，全链路所有递归层操作的都是同一个Storage实例，子层对index的修改会直接同步到上层，不会出现状态不一致的问题。

参考代码示例 #

// Storage类定义参考
class Storage {
    StringBuilder postfix = new StringBuilder();
    int index = 0;
}

// 递归函数实现
public void convert(String prefix, Storage storage) {
    if (storage.index >= prefix.length()) {
        return;
    }
    char curr = prefix.charAt(storage.index);
    // 匹配到操作数，直接拼接后缀、下标后移
    if (Character.isLetter(curr)) {
        storage.postfix.append(curr);
        storage.index++;
        return;
    }
    // 匹配到运算符，先存当前运算符，下标后移
    char op = curr;
    storage.index++;
    // 递归处理左操作数
    convert(prefix, storage);
    // 递归处理右操作数，下标已经是左操作数处理完的最新值
    convert(prefix, storage);
    // 最后拼接运算符
    storage.postfix.append(op);
}

// 初始调用方式
public static void main(String[] args) {
    String input = "-+ABC";
    Storage storage = new Storage();
    new Test().convert(input, storage);
    System.out.println(storage.postfix); // 输出AB+C-，符合预期
}

方案验证 #

针对你给出的测试用例-+ABC，调整后执行逻辑如下：

1. 初始storage.index = 0，匹配到运算符-，下标变为1，先递归处理左操作数
2. 下标1匹配到运算符+，下标变为2，递归处理左操作数
3. 下标2匹配到操作数A，拼接A，下标变为3返回
4. 递归处理+的右操作数，下标3匹配到操作数B，拼接B，下标变为4返回
5. 拼接运算符+，当前后缀为AB+，返回上一层-的处理逻辑
6. 递归处理-的右操作数，下标4匹配到操作数C，拼接C，下标变为5返回
7. 拼接运算符-，最终后缀为AB+C-，和预期结果一致

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