Python 栈示例

# @ignore-function-tree
def check_balanced_parentheses(expr: str, stack: Stack) -> bool:
    """检查表达式是否有成对的括号"""
    brackets = {')': '(', '}': '{', ']': '['}
    
    for char in expr:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.empty() or stack.peek() != brackets[char]:
                return False
            stack.pop()
    
    return stack.empty()

# 使用示例
expr = "{[()]}"
result = check_balanced_parentheses(expr, Stack())

def evaluate_postfix(expr: str, stack: Stack) -> int:
    """
    计算后缀表达式。
    示例："23+" 计算结果为 5
    """
    operators = {'+': lambda x,y: x+y, 
                '-': lambda x,y: x-y,
                '*': lambda x,y: x*y, 
                '/': lambda x,y: x/y}
    
    for char in expr:
        if char.isdigit():
            stack.push(int(char))
        elif char in operators:
            b = stack.pop()
            a = stack.pop()
            stack.push(operators[char](a, b))
    
    return stack.pop()

# 使用示例
evaluate_postfix("23+45*+", Stack())

def reverse_string(s: str, stack: Stack) -> str:
    """
    使用栈反转字符串。
    """
    for char in s:
        stack.push(char)
    
    result = []
    while not stack.empty():
        result.append(stack.pop())
    
    return ''.join(result)

# 使用示例
reverse_string("Hello World!", Stack())

def remove_adjacent_duplicates(s: str, stack: Stack) -> str:
    """
    移除相邻的重复字符。
    """
    for char in s:
        if not stack.empty() and stack.peek() == char:
            stack.pop()
        else:
            stack.push(char)
    
    result = []
    while not stack.empty():
        result.append(stack.pop())
    
    return ''.join(result[::-1])

# 使用示例
remove_adjacent_duplicates("abbaca", Stack())

# @ignore-function-tree
def next_greater_element(arr: List[int], stack: Stack) -> List[int]:
    """
    查找数组中每个元素的下一个更大元素。
    """
    result = [-1] * len(arr)
    
    for i in range(len(arr)):
        while not stack.empty() and arr[stack.peek()] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.push(i)
    
    return result

# 使用示例
next_greater_element([4, 5, 2, 25], Stack())

# @ignore-function-tree
def stock_span(prices: List[int], stack: Stack) -> List[int]:
    """
    计算股票跨度值。
    """
    spans = [1] * len(prices)
    
    for i in range(len(prices)):
        while not stack.empty() and prices[stack.peek()] <= prices[i]:
            stack.pop()
            
        spans[i] = i - stack.peek() if not stack.empty() else i + 1
        stack.push(i)
    
    return spans

# 使用示例
stock_span([100, 80, 60, 70, 60, 75, 85], Stack())

# @ignore-function-tree
def sort_stack(stack: Stack) -> None:
    """
    仅使用栈操作对栈进行升序排序。
    """
    temp_stack = Stack()
    
    while not stack.empty():
        temp = stack.pop()
        
        while not temp_stack.empty() and temp_stack.peek() > temp:
            stack.push(temp_stack.pop())
            
        temp_stack.push(temp)
    
    # 复制回原始栈
    while not temp_stack.empty():
        stack.push(temp_stack.pop())

# 使用示例
stack = Stack()
for x in [3, 1, 4, 1, 5, 9]:
    stack.push(x)
sort_stack(stack)

# @ignore-function-tree
def reverse_stack(stack: Stack) -> None:
    """
    使用递归反转栈。
    """
    def insert_at_bottom(stack: Stack, item: int) -> None:
        if stack.empty():
            stack.push(item)
            return
            
        temp = stack.pop()
        insert_at_bottom(stack, item)
        stack.push(temp)
    
    if not stack.empty():
        temp = stack.pop()
        reverse_stack(stack)
        insert_at_bottom(stack, temp)

# 使用示例
stack = Stack()
for x in [1, 2, 3, 4, 5]:
    stack.push(x)
reverse_stack(stack)

# @ignore-function-tree
def find_pattern_132(arr: List[int], stack: Stack) -> bool:
    """
    查找数组是否包含模式 1-3-2。
    模式：i < j < k 且 arr[i] < arr[k] < arr[j]
    """
    min_values = [float('inf')] * len(arr)
    min_values[0] = arr[0]
    
    for i in range(1, len(arr)):
        min_values[i] = min(min_values[i-1], arr[i])
    
    for j in range(len(arr)-1, -1, -1):
        if arr[j] <= min_values[j]:
            continue
            
        while not stack.empty() and stack.peek() <= min_values[j]:
            stack.pop()
            
        if not stack.empty() and stack.peek() < arr[j]:
            return True
            
        stack.push(arr[j])
    
    return False

# 使用示例
find_pattern_132([3, 1, 4, 2], Stack())

# @ignore-function-tree
def valid_stack_sequence(pushed: List[int], popped: List[int], stack: Stack) -> bool:
    """
    检查序列是否可能通过栈操作生成。
    """
    j = 0
    
    for x in pushed:
        stack.push(x)
        
        while not stack.empty() and j < len(popped) and stack.peek() == popped[j]:
            stack.pop()
            j += 1
    
    return j == len(popped)

# 使用示例
valid_stack_sequence([1,2,3,4,5], [4,5,3,2,1], Stack())