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

Question

我想知道是否有一种方法可以使用2个堆栈在单个传递中解决中缀表达式？堆栈可以是一个用于操作员,另一个用于操作数...

通过分流码算法求解的标准方法是将中缀表达式转换为后缀(反向抛光)然后求解.我不想先将表达式转换为postfix.

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

Answer 1

很晚,但这是答案.

拿两堆:

1. operator stack {为运营商和括号}.
2. operand stack.

算法

如果存在要读取的字符:

1. 如果字符operand按下operand stack,如果是字符(,则按下operator stack.
2. 否则,如果角色是 operator
   1. 虽然顶部的operator stack优先级不是比这个字符小.
   2. operator从中弹出operator stack.
   3. 弹出两个operands(op1和op2)来自operand stack.
   4. 存储op1 op op2在operand stack2.1 的背面.
3. 否则如果角色是),请执行与2.2 - 2.4相同的操作直到遇到(.

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

• 流行操作员直到operator stack不空.
• 弹出顶部2 operands和push op1 op op2上operand stack.

从中返回最高值operand stack.