如何使用堆栈在一次扫描中评估中缀表达式? [英] How to evaluate an infix expression in just one scan using stacks?

问题描述

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

I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...

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

The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.

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

If the expression is like 2*3-(6+5)+8, how to solve?

推荐答案

很晚了，但答案在这里.

Quite late, but here is the answer.

取两堆:

1. operator stack { 用于操作符和括号}.
2. 操作数栈.

1. operator stack { for operators and parentheses }.
2. operand stack.

算法

如果存在要读取的字符:

Algorithm

If character exists to be read:

1. 如果字符是operand，压入operand stack，如果字符是(，压入operand stack>.
2. 否则如果字符是operator

1. If character is operand push on the operand stack, if character is (, push on the operator stack.
2. Else if character is operator

1. 虽然 operator stack 顶部的优先级不低于此字符.
2. 从 operator stack 弹出 operator.
3. 从 operand stack 中弹出两个 operands(op1 和 op2).
4. 将 op1 op op2 存储在 operand stack 回到 2.1.

1. While the top of the operator stack is not of smaller precedence than this character.
2. Pop operator from operator stack.
3. Pop two operands (op1 and op2) from operand stack.
4. Store op1 op op2 on the operand stack back to 2.1.

否则，如果字符是)，则与2.2 - 2.4 相同，直到遇到(.

Else if character is ), do the same as 2.2 - 2.4 till you encounter (.

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

Else (no more character left to read):

• 弹出运算符直到 operator stack 不为空.
• 在 operand stack 上弹出 top 2 operands 和 push op1 op2.

• Pop operators untill operator stack is not empty.
• Pop top 2 operands and push op1 op op2 on the operand stack.

从操作数栈返回顶部值.

这篇关于如何使用堆栈在一次扫描中评估中缀表达式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！