逆波蘭表示法(後綴表達式)將運算符放在運算元之後,消除了括號和優先級歧義,極適合棧式計算。本文實現完整的中綴轉後綴 (Shunting-yard 簡化版)與後綴表達式求值,支持 + - * / ( ) 及多位數整數。
( 直接入棧;) 彈出直到遇到 (。# -*- coding: utf-8 -*-
# 運算符優先級表(數字越大優先級越高)
PRIORITY = {
'#': 0, '(': 1, '+': 2, '-': 2, '*': 3, '/': 3, ')': 4
}
def compare_priority(op, rpn_stack, op_stack):
"""比較當前運算符與棧頂運算符優先級,決定彈出/入棧"""
if not op_stack:
op_stack.append(op)
return
top = op_stack.pop()
p_op = PRIORITY[op]
p_top = PRIORITY[top]
if p_op == p_top:
op_stack.append(top)
op_stack.append(op)
elif p_op > p_top:
op_stack.append(top)
op_stack.append(op)
else: # p_op < p_top
rpn_stack.append(top)
compare_priority(op, rpn_stack, op_stack) # 遞歸處理
def to_rpn(expr):
"""中綴表達式字符串 -> 後綴 token 列表"""
rpn = []
op_stack = []
i = 0
while i < len(expr):
ch = expr[i]
if ch.isdigit():
# 讀取多位數
num = ch
i += 1
while i < len(expr) and expr[i].isdigit():
num += expr[i]
i += 1
rpn.append(num)
continue # 已經移動 i
elif ch == '(':
op_stack.append(ch)
elif ch == ')':
while op_stack:
top = op_stack.pop()
if top == '(':
break
rpn.append(top)
else: # 運算符
compare_priority(ch, rpn, op_stack)
i += 1
# 輸入結束,清空運算符棧
while op_stack:
rpn.append(op_stack.pop())
return rpn
def eval_rpn(rpn_tokens):
"""計算後綴表達式值"""
stack = []
for token in rpn_tokens:
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a / b) # 整除或浮點視需求
return stack.pop()
if __name__ == '__main__':
expr = "3+4*2/(1-5)"
rpn = to_rpn(expr)
print("中綴:", expr)
print("後綴:", ' '.join(rpn))
print("結果:", eval_rpn(rpn))
# 輸出:
# 中綴: 3+4*2/(1-5)
# 後綴: 3 4 2 * 1 5 - / +
# 結果: 1.0
^、函數調用 sin() 等。ast 模塊直接解析 Python 表達式(生產環境推薦)。手寫 RPN 計算器是理解編譯原理「語法分析 + 棧機執行」的最佳入門項目,代碼短小精悍,邏輯清晰優雅。