K*****k
发帖数: 430 | 1 很多数据结构参考书都说,后缀式(逆波兰式)比较适合求值,用一个操作数栈来计算.
但是表达式通常是中缀式，那么如何转为后缀式呢？一种方法是构造中序表达式树，然
后输出后序。但这方法比较麻烦，还有一种方法是利用一个操作符栈结合算符优先级表
，可以把中缀式转为后缀式。
所以分两步走：
1. 一个操作符栈 + 算符优先级表, 中缀式 ->后缀式
2. 后缀式 + 一个操作数栈, 表达式求出结果
但是严蔚敏的数据结构书还介绍了一个经典的方法：
双栈 + 算符优先级表的方法直接对表达式求值，无需引入后缀式的概念。
请问这两种方法是否本质相同？(都涉及了操作符栈，操作数栈和算符优先级表)
严的方法是否就是不显示求出后缀式，但实际上每一步都直接把后缀式的中间计算结果
算出来入栈？ |
|
