Python 實作逆波蘭表示式 (後綴表示式) 運算器

逆波蘭表示式 (RPN) 將運算子置於運算元之後，無需括號即可唯一表示運算順序，適合堆疊機器運算。本文實作中序轉後綴（Shunting-yard 簡化版）與後綴求值完整流程。

演算法流程

1. 掃描輸入：逐字元讀取，數字直接輸出至 RPN 序列，運算子依優先序與堆疊頂端比較決定輸出或入堆疊。
2. 處理括號：左括號入堆疊，右括號彈出直到遇到左括號。
3. 求值：掃描 RPN 序列，數字入堆疊，運算子彈出兩數運算後結果入堆疊，最後堆疊頂為結果。

完整程式碼

# -*- coding: utf-8 -*-
symbol_priority = {
    0: ['#'],
    1: ['('],
    2: ['+', '-'],
    3: ['*', '/'],
    4: [')']
}

def compare_priority(sym, rpn_stack, sym_stack):
    if not sym_stack:
        sym_stack.append(sym)
        return
    top = sym_stack.pop()
    for ops in symbol_priority.values():
        if sym in ops and top in ops:
            sym_stack.extend([top, sym])
            return
        elif sym in ops:
            rpn_stack.append(top)
            compare_priority(sym, rpn_stack, sym_stack)
            return
        elif top in ops:
            sym_stack.extend([top, sym])
            return
    sym_stack.append(top)

def scan_everyone(inp, rpn_stack, sym_stack):
    for ch in inp:
        if ch.isdigit():
            rpn_stack.append(ch)
        else:
            if sym_stack:
                if ch == '(':
                    sym_stack.append(ch)
                elif ch == ')':
                    while True:
                        op = sym_stack.pop()
                        if op == '(':
                            break
                        rpn_stack.append(op)
                else:
                    compare_priority(ch, rpn_stack, sym_stack)
            else:
                sym_stack.append(ch)

def calc_rpn(rpn_stack):
    val_stack = []
    for token in rpn_stack + ['#']:
        if token == '#':
            return val_stack.pop()
        if token.isdigit():
            val_stack.append(token)
        else:
            b = val_stack.pop()
            a = val_stack.pop()
            val_stack.append(str(eval(a + token + b)))
    return val_stack[0]

def main():
    rpn, sym = [], []
    expr = raw_input("輸入中序運算式 (如 3+4*2): ") + '#'
    scan_everyone(expr, rpn, sym)
    # 清空剩餘運算子
    while sym:
        rpn.append(sym.pop())
    print("RPN:", ' '.join(rpn))
    print("結果:", calc_rpn(rpn))

if __name__ == '__main__':
    main()

執行範例

輸入中序運算式 (如 3+4*2): 3+4*2
RPN: 3 4 2 * +
結果: 11

擴展建議

• 支援多位數、浮點數、負數（需詞法分析器）。
• 支援函數 (sin, cos)、冪次 (^)。
• 使用 ast 模組安全評估，避免 eval 風險。

RPN 運算器是編譯器原理與堆疊機器的經典教學範例。