萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實現逆波蘭表達式 (RPN) 計算器:中綴轉後綴與棧式求值

逆波蘭表示法(後綴表達式)將運算符放在運算元之後,消除了括號和優先級歧義,極適合棧式計算。本文實現完整的中綴轉後綴 (Shunting-yard 簡化版)與後綴表達式求值,支持 + - * / ( ) 及多位數整數。

算法流程

  1. 掃描輸入字符串:數字進輸出隊列,運算符進運算符棧,根據優先級決定彈出。
  2. 括號處理:( 直接入棧;) 彈出直到遇到 (。
  3. 輸入結束:將棧中剩餘運算符彈出到輸出隊列。
  4. 求值:掃描後綴表達式,數字入棧,運算符彈出兩個操作數計算後壓回結果。

完整代碼

# -*- 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 計算器是理解編譯原理「語法分析 + 棧機執行」的最佳入門項目,代碼短小精悍,邏輯清晰優雅。

copyright © 萬盛學電腦網 all rights reserved