infix-notation - 如何使用堆栈在一次扫描中计算中缀表达式？

Question

我想知道是否有办法使用 2 个堆栈一次性解决中缀表达式？堆栈可以一个用于运算符，另一个用于操作数...

shunt-yard算法求解的标准方法是将中缀表达式转换为后缀表达式(反向波兰)然后求解。我不想先将表达式转换为后缀。

如果表达式如2*3-(6+5)+8，如何求解？

Answer 1

很晚了，但这是答案。

取两个堆栈:

1. 运算符堆栈 { 用于运算符和括号}。
2. 操作数堆栈。

算法

如果存在要读取的字符:

1. 如果字符是操作数，则压入操作数堆栈，如果字符是(，则压入操作符堆栈 >.
2. Else if 字符是运算符
   1. 虽然运算符堆栈的顶部的优先级不低于该字符。
   2. 从运算符堆栈中弹出运算符。
   3. 从操作数堆栈中弹出两个操作数(op1和op2)。
   4. 将操作数堆栈上的op1 op op2存储回2.1。
3. 否则如果字符是)，则执行与2.2 - 2.4相同的操作，直到遇到(。

否则(没有更多字符可供阅读):

• 弹出运算符，直到运算符堆栈不为空。
• 在操作数堆栈上弹出前 2 个操作数并压入 op1 op op2。

从操作数堆栈返回顶部值。