中缀转后缀表达式转换结果不符，求排查Java代码问题

我最近写了个Java程序用来把中缀表达式转成后缀（逆波兰）表达式，测试25*1-(8+3)/4+2这个表达式的时候，得到的结果是[25, 1, *, -, 8, (, 3, +, 4, /, ), 2, +]，但正确的结果应该是[25, 1, *, 8, 3, +, 4, /, -, 2, +]。我对比过同类转换器的逻辑，还是没找到问题在哪，有没有大佬能帮我排查下？

我的代码大概是这样的：

package calTest;
import java.util.ArrayList;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Calc2 {
    public static ArrayList<String> infixToPostfix(String expression) {
        ArrayList<String> postfix = new ArrayList<>();
        Stack<String> operatorStack = new Stack<>();
        // 用正则匹配数字和运算符
        Pattern pattern = Pattern.compile("\\d+|[-+*/()]");
        Matcher matcher = pattern.matcher(expression);
        
        while (matcher.find()) {
            String token = matcher.group();
            if (token.matches("\\d+")) {
                // 数字直接加入后缀列表
                postfix.add(token);
            } else if (token.equals("(")) {
                // 左括号入栈
                operatorStack.push(token);
            } else if (token.equals(")")) {
                // 右括号：弹出栈顶直到遇到左括号
                while (!operatorStack.isEmpty() && !operatorStack.peek().equals("(")) {
                    postfix.add(operatorStack.pop());
                }
                // 弹出左括号，不加入结果
                if (!operatorStack.isEmpty()) {
                    operatorStack.pop();
                }
            } else {
                // 处理运算符，按优先级弹出栈顶
                while (!operatorStack.isEmpty() && getPriority(operatorStack.peek()) >= getPriority(token)) {
                    postfix.add(operatorStack.pop());
                }
                operatorStack.push(token);
            }
        }
        // 弹出剩余运算符
        while (!operatorStack.isEmpty()) {
            postfix.add(operatorStack.pop());
        }
        return postfix;
    }
    
    // 判断运算符优先级
    private static int getPriority(String operator) {
        switch (operator) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                return 0;
        }
    }
    
    public static void main(String[] args) {
        String expression = "25*1-(8+3)/4+2";
        ArrayList<String> result = infixToPostfix(expression);
        System.out.println(result);
    }
}

问题排查方向 #

从你得到的错误结果来看，核心问题是左括号(和右括号)被错误地加入了后缀列表，同时运算符的弹出顺序也不对。大概率是这几个地方出了问题：

1. token类型判断逻辑错误：你看错误结果里有8, (, 3，说明(没有被识别成左括号去入栈，反而被当成普通token直接加入了后缀列表。检查下你的代码里，判断token.equals("(")的分支是不是没走对——比如有没有把字符串比较写成了==，或者正则匹配出了问题，导致(的token没被正确捕获？
2. 右括号处理漏了弹出左括号：如果遇到)时，没有把栈里的(弹出去，反而让(留在栈里，最后被一起弹出加入结果，也会出现这个问题。确保处理)的分支里，在弹出所有中间运算符后，一定要弹出栈顶的(，并且不要把它加入后缀列表。
3. 优先级判断逻辑错误：如果你的getPriority方法把(的优先级设得太高，比如和加减一样，那处理-的时候就会错误弹出(，但从你的代码来看这个方法是对的，不过还是可以再确认下。

快速修复建议 #

先检查token.equals("(")的判断是不是用了==而不是equals()——Java里字符串比较必须用equals()，用==会因为引用不同导致判断失败，这样(就会走到else分支，被当成普通运算符处理，甚至直接加入后缀列表。如果是这个问题，把==改成equals()就解决了。

另外，在处理)的分支里，一定要加个判断：弹出(后，不要把它加入结果，你的代码里这部分是对的，但如果栈为空的时候调用pop()会报错，所以那层if (!operatorStack.isEmpty())很重要。

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