二、堆疊（stack）可應用於後序表示式（postfix expression）的運算處理，請利用下列的 表示式，繪出堆疊內的變化來說明如何利用堆疊計算其結果，並請寫出演算法。 後序表示式：4 8 – 9 3 / *（該表示式中的數值均為個位數）。（10 分）

詳解 (共 1 筆)

詳解 提供者：hchungw
def evaluate_postfix(expression):
    stack = []
    operators = set(['+', '-', '*', '/'])
    for token in expression.split():
        if token not in operators:
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == '+':
                result = operand1 + operand2
            elif token == '-':
                result = operand1 - operand2
            elif token == '*':
                result = operand1 * operand2
            elif token == '/':
                result = operand1 / operand2  # Python division results in float
            stack.append(result)
    return stack.pop()
# 使用例子
expression = "4 8 - 9 3 / *"
result = evaluate_postfix(expression)
print("Result of postfix expression:", result)
這個演算法中，我們使用一個堆疊來存儲操作數，並根據讀到的操作符進行相應的計算。每當讀到一個操作符，就從堆疊中彈出兩個操作數，進行計算，並將結果推回堆疊。最終堆疊中的唯一值即為表達式的結果。

為了說明如何利用堆疊來計算後序表示式 48−93/∗4 8 - 9 3 / *48−93/∗，我們將一步步展示堆疊內的變化，並給出相應的算法。

後序表示式 48−93/∗4 8 - 9 3 / *48−93/∗ 的計算步驟

  1. 初始狀態：

    • 表示式：4 8 - 9 3 / *
    • 堆疊：[]

  2. 讀取 4：

    • 堆疊：444

  3. 讀取 8：

    • 堆疊：4,84, 84,8

  4. 讀取 -：

    • 從堆疊中彈出兩個元素 8 和 4，計算 4−84 - 84−8
    • 4−8=−44 - 8 = -44−8=−4
    • 將結果 -4 推入堆疊
    • 堆疊：−4-4−4

  5. 讀取 9：

    • 堆疊：−4,9-4, 9−4,9

  6. 讀取 3：

    • 堆疊：−4,9,3-4, 9, 3−4,9,3

  7. 讀取 /：

    • 從堆疊中彈出兩個元素 3 和 9，計算 9/39 / 39/3
    • 9/3=39 / 3 = 39/3=3
    • 將結果 3 推入堆疊
    • 堆疊：−4,3-4, 3−4,3

  8. **讀取 ***：

    • 從堆疊中彈出兩個元素 3 和 -4，計算 −4∗3-4 * 3−4∗3
    • −4∗3=−12-4 * 3 = -12−4∗3=−12
    • 將結果 -12 推入堆疊
    • 堆疊：−12-12−12

最終結果在堆疊的頂部，即 −12-12−12。

演算法

以下是一個基於堆疊的後序表示式計算演算法：