You need to enable JavaScript to run this app. Java双栈实现波兰表示法求值:交替出现类型转换与空栈异常
优惠活动
大模型
产品
解决方案
定价
更多

Java双栈实现波兰表示法求值:交替出现类型转换与空栈异常

波兰(前缀)表示法求值代码问题排查

代码现存核心问题

  • switch分支缺失break语句:每个运算分支执行完会直接穿透到后续分支,比如完成加法计算压入结果后,会继续执行减法、乘法、除法的弹出逻辑,连续从stack2中弹出元素,极易触发空栈异常,最终计算结果完全偏离预期。
  • 循环终止条件取值错误:使用stack.capacity()*2作为循环次数,Java中该方法返回的是栈内部存储数组的扩容容量,不是栈内当前的有效元素个数,计算出的循环次数和实际需要处理的token数完全不匹配,会出现循环提前退出、栈为空仍尝试弹出元素的问题。
  • 初始弹出逻辑无前置校验:进入evaluate方法后无任何判断,直接弹出原栈两个元素压入stack2,未校验弹出的元素是否为操作数,一旦弹出运算符,后续执行数值转换时会直接抛出类转换异常。
  • 运算结果压栈逻辑和初始设计脱节:最初的设计思路是将计算结果压回原栈做归约,但实际实现中所有计算结果都压入stack2,多层嵌套的表达式无法逐层简化,根本无法完成复杂表达式的求值。
  • 栈未指定泛型类型:直接使用原生无类型的Stack类,栈内会混合存储String、int、double等多种类型的元素,后续强转String时就会触发类型转换异常。
  • 方法结构错配:evaluate方法中for循环结束后多写了一个闭合大括号,直接导致编译失败。

可行实现方案

波兰表示法的求值不需要双栈结构,使用单栈从表达式末尾向前遍历即可完成,逻辑简洁且能规避大部分空栈、类型混乱问题:

  1. 按空格将输入表达式拆分为独立token列表
  2. 从列表末尾向前逐个遍历token
  3. 遇到操作数时,将其转为数值类型压入计算栈
  4. 遇到运算符时,连续从栈顶弹出两个数值,按运算符规则计算后将结果压回栈
  5. 遍历完成后,栈中剩余的唯一元素就是表达式的最终求值结果

修正后可运行代码

import java.util.Stack;

public class Main {
    public static void evaluate(String expression) {
        String[] tokens = expression.split(" ");
        // 指定栈存储数值类型,从根源避免类型混乱
        Stack<Double> calcStack = new Stack<>();

        // 从表达式末尾向前遍历,匹配前缀表达式的求值规则
        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                double op1 = calcStack.pop();
                double op2 = calcStack.pop();
                double result;
                // 传统分支实现计算,兼容所有Java版本
                if (token.equals("+")) {
                    result = op1 + op2;
                } else if (token.equals("-")) {
                    result = op1 - op2;
                } else if (token.equals("*")) {
                    result = op1 * op2;
                } else {
                    result = op1 / op2;
                }
                calcStack.push(result);
            } else {
                calcStack.push(Double.parseDouble(token));
            }
        }
        System.out.println("表达式求值结果: " + calcStack.pop());
    }

    public static void main(String[] args) {
        String examplestr = "* + * + 1 2 + 3 4 5 6";
        evaluate(examplestr);
    }
}

示例表达式* + * + 1 2 + 3 4 5 6的正确求值结果为156,运行上述代码可直接得到对应输出。

内容的提问来源于stack exchange,提问作者Selçuk Başaran

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.09 23:36:04