有括號的表達式

 處理含有括號的表達式，同時考慮運算優先順序（乘除優先於加減），可以將中序表達式轉換為後序表達式。括號會影響運算順序，因此需要按照括號優先的規則來處理。

中序轉後序的演算法（含括號）

1. 數字：直接加入後序輸出序列。
2. 左括號 (：推入運算符堆疊。
3. 右括號 )：將運算符堆疊中的符號依次彈出，直到遇到左括號 (，並將左括號丟棄。
4. 運算符（例如 +, -, *, /）：
   • 比較該運算符與堆疊頂端運算符的優先順序。
   • 如果堆疊頂部的運算符優先順序較高或相等，則將堆疊頂端的運算符彈出並加入輸出序列。
   • 將當前運算符推入堆疊。
5. 清理堆疊：當讀完所有的項目後，將堆疊中剩餘的運算符依次彈出並加入輸出序列。

以下是完整的 Python 程式碼來實現這個過程：

程式碼

# 輸入數學表達式，例如："( 1 + 2 ) * 3"
expression = input("輸入數學表達式，例如 '( 1 + 2 ) * 3': ")

# 步驟 1：把數字和符號分開
tokens = []
for i in expression.split():
    if i.isdigit():           # 如果 i 是數字
        tokens.append(int(i))  # 把數字轉為 int 並加入 tokens
    else:
        tokens.append(i)       # 把符號直接加到 tokens

# 儲存後序表達式的結果
output = []
# 儲存運算符的堆疊
operators = []

# 定義運算符的優先順序
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

# 步驟 2：轉換為後序表達式
for token in tokens:
    if type(token) == int:       # 如果是數字
        output.append(token)     # 直接加入輸出
    elif token == '(':           # 左括號
        operators.append(token)  # 推入堆疊
    elif token == ')':           # 右括號
        # 把堆疊中的運算符彈出，直到遇到左括號
        while operators[-1] != '(':
            output.append(operators.pop())
        operators.pop()          # 丟掉左括號
    else:                        # 如果是運算符
        # 當堆疊中的運算符優先順序比當前運算符高或相等，彈出它們
        while (operators and operators[-1] != '(' and
               precedence[operators[-1]] >= precedence[token]):
            output.append(operators.pop())
        operators.append(token)  # 把當前運算符推入堆疊

# 把剩下的運算符都彈出
while operators:
    output.append(operators.pop())

# 後序表達式已生成
print("後序表達式:", output)

# 步驟 3：計算後序表達式的結果
stack = []

for token in output:
    if type(token) == int:   # 如果是數字，推入堆疊
        stack.append(token)
    else:                    # 如果是運算符，取出兩個數字計算
        b = stack.pop()      # 堆疊頂部的數字為 b
        a = stack.pop()      # 再取出一個數字為 a
        if token == '+':
            stack.append(a + b)
        elif token == '-':
            stack.append(a - b)
        elif token == '*':
            stack.append(a * b)
        elif token == '/':
            stack.append(a / b)  # 確保除數不為 0

# 最後堆疊中只剩一個結果，即為最終計算結果
result = stack[0]
print("結果:", result)

程式說明

1. 解析輸入：將輸入表達式按空格分開，分成數字和符號，存入 tokens 列表中。

2. 轉換為後序表達式：

   • 數字直接加入 output 列表。
   • 左括號 ( 直接推入 operators 堆疊。
   • 右括號 ) 會觸發彈出 operators 堆疊中的運算符，直到遇到左括號為止。
   • 當運算符出現時，根據優先順序彈出堆疊中的運算符，直到當前運算符具有最高優先順序。

3. 計算後序表達式：

   • 用堆疊來計算後序表達式。遇到數字時推入堆疊，遇到運算符時彈出兩個數字並計算結果，再把結果推回堆疊。
   • 最後堆疊中唯一的數字即為結果。

範例執行

輸入：

( 1 + 2 ) * 3

執行過程：

1. 解析 tokens 為 [ '(', 1, '+', 2, ')', '*', 3 ]
2. 轉換為後序表達式：[ 1, 2, '+', 3, '*' ]
3. 後序計算：
   • 1 + 2 = 3
   • 3 * 3 = 9

輸出：

後序表達式: [1, 2, '+', 3, '*']
結果: 9