Java双栈实现波兰表示法求值:交替出现类型转换与空栈异常
波兰(前缀)表示法求值代码问题排查
代码现存核心问题
switch分支缺失break语句:每个运算分支执行完会直接穿透到后续分支,比如完成加法计算压入结果后,会继续执行减法、乘法、除法的弹出逻辑,连续从stack2中弹出元素,极易触发空栈异常,最终计算结果完全偏离预期。- 循环终止条件取值错误:使用
stack.capacity()*2作为循环次数,Java中该方法返回的是栈内部存储数组的扩容容量,不是栈内当前的有效元素个数,计算出的循环次数和实际需要处理的token数完全不匹配,会出现循环提前退出、栈为空仍尝试弹出元素的问题。 - 初始弹出逻辑无前置校验:进入evaluate方法后无任何判断,直接弹出原栈两个元素压入stack2,未校验弹出的元素是否为操作数,一旦弹出运算符,后续执行数值转换时会直接抛出类转换异常。
- 运算结果压栈逻辑和初始设计脱节:最初的设计思路是将计算结果压回原栈做归约,但实际实现中所有计算结果都压入stack2,多层嵌套的表达式无法逐层简化,根本无法完成复杂表达式的求值。
- 栈未指定泛型类型:直接使用原生无类型的
Stack类,栈内会混合存储String、int、double等多种类型的元素,后续强转String时就会触发类型转换异常。 - 方法结构错配:evaluate方法中for循环结束后多写了一个闭合大括号,直接导致编译失败。
可行实现方案
波兰表示法的求值不需要双栈结构,使用单栈从表达式末尾向前遍历即可完成,逻辑简洁且能规避大部分空栈、类型混乱问题:
- 按空格将输入表达式拆分为独立token列表
- 从列表末尾向前逐个遍历token
- 遇到操作数时,将其转为数值类型压入计算栈
- 遇到运算符时,连续从栈顶弹出两个数值,按运算符规则计算后将结果压回栈
- 遍历完成后,栈中剩余的唯一元素就是表达式的最终求值结果
修正后可运行代码
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
相关产品推荐
相关产品推荐

