我想知道是否有一種方法可以使用2個堆棧在一次傳遞中解決中綴表達式？堆?？梢允且粋€用于運算符的堆棧，另一個可以用于操作數的堆棧...用shunt-yard算法求解的標準方法是將中綴表達式轉換為后綴（反向修飾），然后求解。我不想先將表達式轉換為后綴。如果表達式是2*3-(6+5)+8，如何解決？
3 回答
小怪獸愛吃肉
TA貢獻1852條經驗 獲得超1個贊
很晚了，但這是答案。
取兩疊：
operator stack{用于運算符和括號}。operand stack。
算法
如果存在要讀取的字符：
如果
operand按下字符operand stack，如果(按下字符operator stack。否則，如果字符是
operator而的頂部
operator stack優先級比此字符小。operator從彈出operator stack。從中彈出兩個
operands（op1和op2）operand stack。存儲
op1 op op2在operand stack回2.1。否則
)，請執行2.2-2.4的操作，直到遇到為止(。
其他（不再需要閱讀其他字符）：
彈出運算符，直到
operator stack不為空。彈出頂部2，
operands然后push op1 op op2在上operand stack。
返回的最高值operand stack。
慕田峪4524236
TA貢獻1875條經驗 獲得超5個贊
鏈接中給出的方法確實很好。
讓我引用來源：
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.
我希望這有幫助！
添加回答
舉報
0/150
提交
取消