如何使用堆栈在一次扫描中计算内插表达式？

Question

我想知道是否有一种方法可以使用两个堆栈在一次传递中求解中缀表达式？堆栈可以是一个用于运算符，另一个用于操作数。。。

使用分流码算法求解的标准方法是将中缀表达式转换为后缀（反向波兰），然后求解。我不想先将表达式转换为后缀。

如果表达式类似于2*3-（6 5）8，如何求解？

Answer 1

• 创建一个空操作符堆栈。
• 创建一个空操作数堆栈。
• 对于输入字符串中的每个令牌
  a.获取内缀字符串中的下一个令牌。
  b.如果下一个是操作数，则将其放在操作数堆栈上。
  c.如果下一个令牌是运算符
  • 评估操作员。

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.

我希望这有帮助！

Answer 3

很晚了，但答案是这样的。

取两叠：

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

如果字符存在要读取：

1. 如果字符是操作数推压操作数堆栈，如果字符是（），推压运算符堆栈

Else（没有更多字符可读取）：

• 弹出运算符，直到运算符栈不为空。
• 在操作数堆栈上弹出顶部2操作数和推送op1 op op2。

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