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

Question

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

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

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

Answer 1

很晚了，但答案在这里。

取两个堆栈:

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

算法

如果存在要读取的字符:

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

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

• 弹出运算符直到 operator stack 不为空。
• 将前 2 个操作数弹出并push op1 op op2到操作数栈。

从操作数栈返回顶部值。