Java实现调度场算法时Stack压入字符出现堆内存溢出如何解决

问题根本原因 #

你遇到的OOM错误核心是死循环导致栈对象无限扩容：

• Java中String是不可变类，infix.substring(1)会返回新的字符串，但你没有把返回值重新赋值给infix变量，导致while(infix.length() > 0)的条件永远为真，程序会无限循环处理输入字符串的第一个字符。
• 当第一个字符是(时，每次循环都会执行opStack.push(digit)，Stack底层是Vector，每次扩容都会调用Arrays.copyOf复制数组，直到堆内存耗尽，就触发了你看到的报错。

其他需要修复的逻辑bug #

除了死循环问题，你的代码还有多处不符合调度场算法逻辑、会触发运行时错误的问题：

1. 数字处理逻辑错误：
   • 单个数字字符处理时，你给队列加入的是初始化值0，而非当前字符对应的数值
   • 没有处理字符串只剩最后一个字符的场景，直接调用infix.charAt(1)会抛出StringIndexOutOfBoundsException
2. 运算符处理逻辑错误：
   • 处理*//、+/-的循环判断中，没有先判断栈是否为空就调用peek()，会抛出EmptyStackException
3. 调度场算法逻辑缺失：
   • 遍历完所有输入字符后，没有把栈中剩余的所有运算符依次弹出加入后缀队列

修复方案 #

1. 修复死循环 #

把infix.substring(1);改为infix = infix.substring(1);，每次循环截断输入字符串的第一个字符。

2. 修复数字处理逻辑 #

调整数字分支的判断，避免索引越界，单个数字也能正确入队。

3. 修复运算符判断逻辑 #

所有peek()调用前先判断栈是否为空。

4. 补充清栈逻辑 #

循环结束后遍历栈，把剩余运算符全部加入后缀队列。

修复后的完整代码 #

public PostfixQueue(String infix) {
    Stack<Character> opStack = new Stack<Character>();
    PostfixQueue postQueue = new PostfixQueue();
    
    Character currentChar;
    int numDigits = 0, result = 0;
    
    while(infix.length() > 0) {
        currentChar = infix.charAt(0);
        
        switch(currentChar) {
            case '0':case '1':case '2':case '3':case '4':
            case '5':case '6':case '7':case '8':case '9':
                result = (result * 10) + Character.getNumericValue(currentChar);
                numDigits++;
                // 判断下一个字符是否还是数字，且没有越界
                if(infix.length() > 1 && Character.isDigit(infix.charAt(1))) {
                    // 多位数，继续累加
                } else {
                    // 数字结束，入队
                    postQueue.Enqueue(result);
                    numDigits = 0;
                    result = 0;
                }
                break;
            case '+':
            case '-':
                while(!opStack.empty() && opStack.peek() != '(') {
                    postQueue.Enqueue(opStack.pop());
                }
                opStack.push(currentChar);
                break;
            case '*':
            case '/':
                while(!opStack.empty() && (opStack.peek() == '*' || opStack.peek() == '/')) {
                    postQueue.Enqueue(opStack.pop());
                }
                opStack.push(currentChar);
                break;
            case '(':
                opStack.push(currentChar);
                break;
            case ')':
                while(!opStack.empty() && opStack.peek() != '(') {
                    postQueue.Enqueue(opStack.pop());
                }
                if(!opStack.empty()) {
                    opStack.pop(); // 弹出左括号，不加入队列
                }
                break;
            // 可选：处理空格的分支，如果输入有空格可以直接跳过
            case ' ':
                break;
            default:
                // 非法字符可以根据需求抛出异常或者忽略
                throw new IllegalArgumentException("非法字符：" + currentChar);
        }
        // 修复死循环：把截断后的字符串重新赋值给infix
        infix = infix.substring(1);
    }
    // 调度场算法最后要把栈内剩余运算符全部弹出
    while(!opStack.empty()) {
        postQueue.Enqueue(opStack.pop());
    }
    this.first = postQueue.GetFirst();
}

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