Python入棧出棧解析

解析Python中的入棧和出棧操作，包括示例代碼。

一、棧的概念

棧是一種遵循後進先出（LIFO）原則的一組元素的集合，即最後進入的元素最先被取出。棧可以簡單地實現為一個容器，可以在末尾進行插入和刪除操作。棧的插入操作被稱為入棧（push），刪除操作被稱為出棧（pop）。

二、Python中的棧實現

Python使用list列表作為棧的底層實現方式。list作為一種動態數組，可以方便地進行插入和刪除操作。通過將元素添加到list的末尾實現入棧操作，將末尾元素刪除即可實現出棧操作。

stack = [] #創建一個空棧

#入棧
stack.append("apple")
stack.append("orange")
stack.append("banana")

#出棧
stack.pop()

三、使用棧解決問題

棧可以用於許多應用問題的解決，如括號匹配、表達式求值等。

1. 括號匹配

括號匹配是指對於給定的一個字符串，判斷其中的括號是否匹配。例如”()[]{}”和”[{()}]”是匹配的，而”([)]”則不匹配。

使用棧可以解決該問題，遍歷字符串中的每一個字符，如果遇到左括號即入棧，如果遇到右括號即出棧並判斷是否與棧頂元素匹配。

def match_parentheses(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    
    for c in s:
        if c in mapping:
            #遇到右括號，出棧並判斷與棧頂元素是否匹配
            top_element = stack.pop() if stack else "#"
            if mapping[c] != top_element:
                return False
        else:
            #遇到左括號，入棧
            stack.append(c)

    #棧為空則所有括號都匹配了
    return not stack

2. 表達式求值

使用棧可以解決表達式求值問題。遍歷表達式，遇到數字直接入棧，遇到運算符則彈出棧頂兩個元素進行運算，並將結果入棧。最後剩下的棧頂元素即為表達式的結果。

def eval_expression(s: str) -> int:
    stack = []
    operand = 0
    result = 0
    sign = 1
    
    for c in s:
        if c.isdigit():
            operand = operand * 10 + int(c)
        elif c == '+':
            #將算式結果累加到最後的結果中
            result += sign * operand
            #重置操作數和正負號
            operand = 0
            sign = 1
        elif c == '-':
            #將算式結果累加到最後的結果中
            result += sign * operand
            #重置操作數和正負號
            operand = 0
            sign = -1
        elif c == '(':
            #入棧當前的算式結果和正負號
            stack.append(result)
            stack.append(sign)
            #重置結果和正負號
            result = 0
            sign = 1
        elif c == ')':
            #將棧頂的正負號和算式結果結合起來
            result += sign * operand
            operand = 0
            
            pre_sign = stack.pop()
            pre_operand = stack.pop()
            
            result = pre_operand + pre_sign * result

    #最後的算式結果
    return result + sign * operand

四、總結

Python中使用list實現棧結構，方便進行入棧出棧操作。棧可以實現許多常見問題的解決，如括號匹配、表達式求值等。希望今天的內容讓您更好地理解Python的棧操作。感謝閱讀！