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

Question

我想知道是否有一种方法可以使用2个堆栈在一次传递中解决中缀表达式？堆栈可以是一个用于运算符的堆栈，另一个可以用于操作数的堆栈...用shunt-yard算法求解的标准方法是将中缀表达式转换为后缀（反向修饰），然后求解。我不想先将表达式转换为后缀。如果表达式是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 stack回2.1。

3. 否则)，请执行2.2-2.4的操作，直到遇到为止(。

其他（不再需要阅读其他字符）：

• 弹出运算符，直到operator stack不为空。

• 弹出顶部2，operands然后push op1 op op2在上operand stack。

返回的最高值operand stack。

Answer 2

链接中给出的方法确实很好。

让我引用来源：

We will use two stacks:

Operand stack: to keep values (numbers)  and

Operator stack: to keep operators (+, -, *, . and ^).  

In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator  value2 (v) push the value obtained in operand stack.          

Algorithm:

Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):

(a) If the character is an operand, push it onto the operand stack.

(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.

(c) If the character is an operator and the operator stack is not empty, and the character's precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.

(d) If the character is "(", then push it onto operator stack.

(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack.  At this stage POP the operator stack and ignore "(."

(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.

 When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression.

我希望这有帮助！