第7章 栈与表达式求值理论

本章导读

栈是最基础的线性数据结构之一，其LIFO（后进先出）特性使其成为函数调用、表达式求值、语法分析等核心应用的基础。本章从形式化角度深入分析栈的数学基础，包括栈ADT规范、单调栈算法理论、表达式求值的正确性证明，以及栈在编译原理中的应用。

学习目标

完成本章学习后，读者将能够：

• 掌握栈ADT的形式化规范与公理系统
• 理解单调栈算法的理论基础与复杂度分析
• 掌握表达式求值的Dijkstra双栈算法
• 理解递归与栈的关系及尾递归优化
• 掌握栈在语法分析中的应用

---

7.1 栈的形式化理论

7.1.1 栈的数学定义

定义 7.1（栈） 栈是一个有序序列 $S = \langle s_1, s_2, \ldots, s_n \rangle$，支持在一端（栈顶）进行插入和删除操作。

定义 7.2（栈操作） 栈支持以下基本操作：

• $push(S, x) = \langle s_1, \ldots, s_n, x \rangle$：将 $x$ 压入栈顶
• $pop(S) = \langle s_1, \ldots, s_{n-1} \rangle$：弹出栈顶元素
• $top(S) = s_n$：返回栈顶元素
• $isEmpty(S) = (n = 0)$：判断栈是否为空

定义 7.3（LIFO性质） 栈满足后进先出性质：最后压入的元素最先被弹出。

$$\forall S, x: top(push(S, x)) = x$$

$$\forall S, x: pop(push(S, x)) = S$$

7.1.2 栈ADT规范

ADT 7.1（Stack）

ADT Stack[T]
  Types: Stack[T]
  
  Operations:
    empty: → Stack[T]
    push: Stack[T] × T → Stack[T]
    pop: Stack[T] → Stack[T]
    top: Stack[T] → T
    isEmpty: Stack[T] → Boolean
    size: Stack[T] → ℕ
  
  Axioms:
    ∀s: Stack[T], ∀x: T
    (A1) isEmpty(empty) = true
    (A2) isEmpty(push(s, x)) = false
    (A3) top(push(s, x)) = x
    (A4) pop(push(s, x)) = s
    (A5) size(empty) = 0
    (A6) size(push(s, x)) = size(s) + 1
    (A7) pop(empty) = error
    (A8) top(empty) = error

定理 7.1（栈ADT一致性） 栈ADT的公理系统是一致的。

证明：构造列表模型。设栈为列表 $L$，栈顶为列表末尾。

• $empty = []$
• $push(L, x) = L + [x]$
• $pop(L) = L[0..|L|-2]$（当 $L \neq []$）
• $top(L) = L[|L|-1]$（当 $L \neq []$）
• $isEmpty(L) = (L = [])$

可直接验证所有公理成立。∎

定理 7.2（栈操作的唯一性） 栈的任何状态可以唯一地表示为从空栈开始的一系列push操作的结果。

证明：对栈中元素数量进行归纳。

基础情况：空栈 = $empty$，唯一。

归纳步骤：设栈 $S$ 有 $n$ 个元素，$S = \langle s_1, \ldots, s_n \rangle$。由公理 (A4)：

$$S = push(pop(S), top(S))$$

由归纳假设，$pop(S)$ 可以唯一表示，故 $S$ 也可以唯一表示。∎

7.1.3 栈的代数结构

定义 7.4（栈代数） 栈上的操作构成一个代数结构，满足：

$$push(pop(S), x) \neq S \quad \text{（一般情况）}$$

$$pop(push(S, x)) = S \quad \text{（公理 A4）}$$

这表明 $push$ 和 $pop$ 不是逆运算对，而是满足特定的代数关系。

定理 7.3（栈的不变量） 对于任意栈 $S$ 和元素序列 $x_1, x_2, \ldots, x_k$：

$$pop^k(push(S, x_1) \circ push(x_2) \circ \ldots \circ push(x_k)) = S$$

其中 $pop^k$ 表示连续 $k$ 次 $pop$ 操作。

证明：对 $k$ 进行归纳。基础情况 $k=0$ 显然。归纳步骤：

$$pop^{k+1}(push(S, x_1) \circ \ldots \circ push(x_{k+1}))$$ $$= pop^k(pop(push(S, x_1) \circ \ldots \circ push(x_k)) \circ push(x_{k+1}))$$ $$= pop^k(push(S, x_1) \circ \ldots \circ push(x_k)) \quad \text{（由公理 A4）}$$ $$= S \quad \text{（由归纳假设）}$$

∎

---

7.2 栈的实现与复杂度分析

7.2.1 基于数组的实现

定理 7.4（数组栈复杂度） 基于动态数组的栈实现，各操作的均摊时间复杂度为：

操作	均摊时间	最坏时间
push	$O(1)$	$O(n)$
pop	$O(1)$	$O(1)$
top	$O(1)$	$O(1)$

证明：push 操作可能触发数组扩容，但由均摊分析（第2章定理2.6），$n$ 次 push 的总代价为 $O(n)$，故均摊代价为 $O(1)$。pop 和 top 不涉及扩容，为 $O(1)$。∎

7.2.2 基于链表的实现

定理 7.5（链表栈复杂度） 基于单链表的栈实现，各操作的最坏时间复杂度均为 $O(1)$。

证明：在链表头部插入和删除都是 $O(1)$ 操作，无需扩容。∎

7.2.3 栈实现

from typing import TypeVar, Generic, List, Optional, Iterator

T = TypeVar('T')

class ArrayStack(Generic[T]):
    """
    基于动态数组的栈实现
    
    时间复杂度：
    - push: O(1) 均摊
    - pop: O(1)
    - top: O(1)
    
    空间复杂度：O(n)
    """
    
    def __init__(self, capacity: int = 10):
        self._data: List[Optional[T]] = [None] * capacity
        self._size = 0
    
    def push(self, item: T) -> None:
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        self._data[self._size] = item
        self._size += 1
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        self._size -= 1
        item = self._data[self._size]
        self._data[self._size] = None
        
        if 0 < self._size < len(self._data) // 4:
            self._resize(len(self._data) // 2)
        
        return item
    
    def top(self) -> T:
        if self.is_empty():
            raise IndexError("top from empty stack")
        return self._data[self._size - 1]
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    def __len__(self) -> int:
        return self._size
    
    def _resize(self, capacity: int) -> None:
        old = self._data
        self._data = [None] * capacity
        for i in range(self._size):
            self._data[i] = old[i]
    
    def __iter__(self) -> Iterator[T]:
        for i in range(self._size - 1, -1, -1):
            yield self._data[i]
    
    def __repr__(self) -> str:
        return f"ArrayStack({list(self)})"


class LinkedStack(Generic[T]):
    """
    基于单链表的栈实现
    
    时间复杂度：所有操作 O(1) 最坏情况
    空间复杂度：O(n)，每个元素一个节点
    """
    
    class _Node:
        __slots__ = ['_value', '_next']
        
        def __init__(self, value: T, next_node: Optional['LinkedStack._Node'] = None):
            self._value = value
            self._next = next_node
    
    def __init__(self):
        self._head: Optional[LinkedStack._Node] = None
        self._size = 0
    
    def push(self, item: T) -> None:
        self._head = self._Node(item, self._head)
        self._size += 1
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node._next
        self._size -= 1
        return node._value
    
    def top(self) -> T:
        if self.is_empty():
            raise IndexError("top from empty stack")
        return self._head._value
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    def __len__(self) -> int:
        return self._size
    
    def __iter__(self) -> Iterator[T]:
        current = self._head
        while current:
            yield current._value
            current = current._next
    
    def __repr__(self) -> str:
        return f"LinkedStack({list(self)})"

---

7.3 表达式求值理论

7.3.1 表达式的形式化定义

定义 7.5（算术表达式） 算术表达式的语法（BNF）：

$$E \to E + E \mid E - E \mid E * E \mid E / E \mid (E) \mid num$$

定义 7.6（运算符优先级） 定义运算符的优先级关系：

运算符	优先级	结合性
$+$, $-$	1	左结合
$*$, $/$	2	左结合
$\wedge$	3	右结合

定义 7.7（中缀、前缀、后缀表达式）

• 中缀表达式：$a + b$，运算符在操作数之间
• 前缀表达式（波兰表示法）：$+ a b$，运算符在操作数之前
• 后缀表达式（逆波兰表示法）：$a b +$，运算符在操作数之后

定理 7.6（表达式等价性） 对于不含括号的表达式，中缀、前缀、后缀三种表示法是等价的，可以相互转换。

证明：通过表达式树证明。三种表示法对应于表达式树的三种遍历方式：

• 中缀：中序遍历
• 前缀：前序遍历
• 后缀：后序遍历

由于表达式树唯一确定表达式，三种表示法等价。∎

7.3.2 中缀转后缀算法

算法 7.1（Shunting-yard算法） Dijkstra的调度场算法将中缀表达式转换为后缀表达式。

定理 7.7（Shunting-yard正确性） Shunting-yard算法正确地将中缀表达式转换为等价的后缀表达式。

证明：通过分析运算符栈的行为：

1. 操作数直接输出，保持相对顺序
2. 运算符在栈中按优先级排列
3. 遇到更高优先级运算符时，先输出栈顶较低优先级运算符
4. 括号保证子表达式的完整性

因此，输出序列是正确的后缀表达式。∎

from typing import List, Union

def infix_to_postfix(expression: str) -> List[Union[str, float]]:
    """
    中缀表达式转后缀表达式（Shunting-yard算法）
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    right_associative = {'^'}
    
    output: List[Union[str, float]] = []
    operators: List[str] = []
    
    i = 0
    while i < len(expression):
        char = expression[i]
        
        if char.isspace():
            i += 1
            continue
        
        if char.isdigit() or char == '.':
            j = i
            while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                j += 1
            output.append(float(expression[i:j]))
            i = j
            continue
        
        if char == '(':
            operators.append(char)
        elif char == ')':
            while operators and operators[-1] != '(':
                output.append(operators.pop())
            operators.pop()
        else:
            while (operators and operators[-1] != '(' and
                   (precedence.get(operators[-1], 0) > precedence.get(char, 0) or
                    (precedence.get(operators[-1], 0) == precedence.get(char, 0) and
                     char not in right_associative))):
                output.append(operators.pop())
            operators.append(char)
        
        i += 1
    
    while operators:
        output.append(operators.pop())
    
    return output


def evaluate_postfix(postfix: List[Union[str, float]]) -> float:
    """
    计算后缀表达式
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    stack: List[float] = []
    
    for token in postfix:
        if isinstance(token, float):
            stack.append(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)
            elif token == '^':
                stack.append(a ** b)
    
    return stack[0]


def evaluate_expression(expression: str) -> float:
    """计算中缀表达式"""
    postfix = infix_to_postfix(expression)
    return evaluate_postfix(postfix)

7.3.3 Dijkstra双栈算法

算法 7.2（双栈表达式求值） Dijkstra双栈算法直接计算中缀表达式。

定理 7.8（双栈算法正确性） Dijkstra双栈算法正确计算含括号的中缀表达式。

证明：分析两个栈的状态：

1. 值栈：存储操作数和中间结果
2. 运算符栈：存储未处理的运算符

当遇到右括号时，执行栈顶运算，保证运算顺序正确。当表达式结束时，栈中剩余运算按优先级执行。

通过归纳法可证明算法正确性。∎

def dijkstra_two_stack(expression: str) -> float:
    """
    Dijkstra双栈表达式求值算法
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    values: List[float] = []
    operators: List[str] = []
    
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    
    def apply_operator():
        op = operators.pop()
        b = values.pop()
        a = values.pop()
        
        if op == '+':
            values.append(a + b)
        elif op == '-':
            values.append(a - b)
        elif op == '*':
            values.append(a * b)
        elif op == '/':
            values.append(a / b)
    
    i = 0
    while i < len(expression):
        char = expression[i]
        
        if char.isspace():
            i += 1
            continue
        
        if char.isdigit() or char == '.':
            j = i
            while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                j += 1
            values.append(float(expression[i:j]))
            i = j
            continue
        
        if char == '(':
            operators.append(char)
        elif char == ')':
            while operators and operators[-1] != '(':
                apply_operator()
            operators.pop()
        elif char in '+-*/':
            while (operators and operators[-1] != '(' and
                   precedence.get(operators[-1], 0) >= precedence.get(char, 0)):
                apply_operator()
            operators.append(char)
        
        i += 1
    
    while operators:
        apply_operator()
    
    return values[0]

---

7.4 单调栈理论

7.4.1 单调栈的定义

定义 7.8（单调栈） 单调栈是一种特殊的栈，其元素保持单调递增或单调递减的顺序。

• 单调递增栈：栈底到栈顶元素递增
• 单调递减栈：栈底到栈顶元素递减

定理 7.9（单调栈性质） 单调栈可以在 $O(n)$ 时间内解决"下一个更大/更小元素"类问题。

证明：每个元素最多入栈一次、出栈一次，因此总操作次数为 $O(n)$。∎

7.4.2 下一个更大元素问题

问题 7.1 给定数组 $A[0..n-1]$，对每个元素找出右边第一个比它大的元素。

算法 7.3（单调递减栈）

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    """
    找出每个元素右边第一个比它大的元素
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    
    使用单调递减栈
    """
    n = len(nums)
    result = [-1] * n
    stack: List[int] = []
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result


def next_greater_element_circular(nums: List[int]) -> List[int]:
    """
    循环数组的下一个更大元素
    
    时间复杂度：O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack: List[int] = []
    
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)
    
    return result

7.4.3 柱状图最大矩形

问题 7.2 给定柱状图的高度数组，找出最大矩形面积。

定理 7.10（最大矩形算法） 使用单调栈可以在 $O(n)$ 时间内求解柱状图最大矩形问题。

证明：对于每个柱子 $i$，找到其左右边界：

• 左边界：左边第一个比 $heights[i]$ 小的柱子
• 右边界：右边第一个比 $heights[i]$ 小的柱子

以柱子 $i$ 为高度的最大矩形面积为 $heights[i] \times (right - left - 1)$。

使用单调递增栈可以同时找到左右边界。∎

def largest_rectangle_area(heights: List[int]) -> int:
    """
    柱状图最大矩形面积
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    stack: List[int] = []
    max_area = 0
    heights = heights + [0]
    
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    return max_area


def largest_rectangle_histogram(heights: List[int]) -> int:
    """
    显式计算左右边界的实现
    """
    n = len(heights)
    
    left = [-1] * n
    stack: List[int] = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    right = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    max_area = 0
    for i in range(n):
        max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))
    
    return max_area

7.4.4 接雨水问题

问题 7.3 给定高度数组，计算能接多少雨水。

定理 7.11（接雨水算法） 使用单调栈可以在 $O(n)$ 时间内求解接雨水问题。

def trap_rain_water(height: List[int]) -> int:
    """
    接雨水问题
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    
    思路：对于每个位置，能接的雨水 = min(左边最高, 右边最高) - 当前高度
    """
    if not height:
        return 0
    
    stack: List[int] = []
    water = 0
    
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[bottom]
            water += distance * bounded_height
        
        stack.append(i)
    
    return water


def trap_rain_water_two_pointer(height: List[int]) -> int:
    """
    双指针解法
    
    时间复杂度：O(n)
    空间复杂度：O(1)
    """
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    
    return water

---

7.5 递归与栈

7.5.1 递归的栈模型

定义 7.9（调用栈） 函数调用时，系统将返回地址、参数、局部变量压入调用栈；函数返回时，从栈中弹出这些信息。

定理 7.12（递归与栈的等价性） 任何递归算法都可以用显式栈转换为迭代算法。

证明：递归调用隐式使用调用栈。通过显式维护栈，可以模拟递归过程：

1. 将初始参数压栈
2. 循环处理栈顶状态
3. 遇到递归调用时，将新状态压栈
4. 处理完返回时弹栈

这完全模拟了递归的执行过程。∎

7.5.2 尾递归优化

定义 7.10（尾递归） 若递归调用是函数的最后操作，则称为尾递归。

定理 7.13（尾递归优化） 尾递归可以优化为迭代，空间复杂度从 $O(n)$ 降为 $O(1)$。

证明：尾递归不需要保存返回后的状态，因此可以复用当前栈帧。编译器可以将其优化为跳转指令。∎

def factorial_recursive(n: int) -> int:
    """普通递归 - O(n) 空间"""
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)


def factorial_tail_recursive(n: int, acc: int = 1) -> int:
    """尾递归 - 可优化为 O(1) 空间"""
    if n <= 1:
        return acc
    return factorial_tail_recursive(n - 1, n * acc)


def factorial_iterative(n: int) -> int:
    """迭代版本 - O(1) 空间"""
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


def factorial_stack(n: int) -> int:
    """显式栈模拟递归"""
    stack: List[int] = []
    
    while n > 1:
        stack.append(n)
        n -= 1
    
    result = 1
    while stack:
        result *= stack.pop()
    
    return result

7.5.3 深度优先搜索的栈实现

from typing import Dict, List, Set, TypeVar

T = TypeVar('T')

def dfs_recursive(graph: Dict[T, List[T]], start: T, visited: Set[T] = None) -> List[T]:
    """递归DFS"""
    if visited is None:
        visited = set()
    
    result = []
    
    if start not in visited:
        visited.add(start)
        result.append(start)
        for neighbor in graph.get(start, []):
            result.extend(dfs_recursive(graph, neighbor, visited))
    
    return result


def dfs_stack(graph: Dict[T, List[T]], start: T) -> List[T]:
    """
    栈实现DFS
    
    时间复杂度：O(V + E)
    空间复杂度：O(V)
    """
    visited: Set[T] = set()
    result: List[T] = []
    stack: List[T] = [start]
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

---

7.6 高级应用

7.6.1 最小栈

问题 7.4 设计一个支持 $O(1)$ 获取最小值的栈。

定理 7.14（最小栈正确性） 使用辅助栈存储最小值，可以在 $O(1)$ 时间内获取当前最小值。

class MinStack:
    """
    最小栈实现
    
    时间复杂度：所有操作 O(1)
    空间复杂度：O(n)
    """
    
    def __init__(self):
        self._stack: List[int] = []
        self._min_stack: List[int] = []
    
    def push(self, val: int) -> None:
        self._stack.append(val)
        if not self._min_stack or val <= self._min_stack[-1]:
            self._min_stack.append(val)
    
    def pop(self) -> int:
        val = self._stack.pop()
        if val == self._min_stack[-1]:
            self._min_stack.pop()
        return val
    
    def top(self) -> int:
        return self._stack[-1]
    
    def get_min(self) -> int:
        return self._min_stack[-1]


class MinStackOptimized:
    """
    优化的最小栈（单栈实现）
    
    使用元组 (value, current_min) 存储
    """
    
    def __init__(self):
        self._stack: List[tuple] = []
        self._min = float('inf')
    
    def push(self, val: int) -> None:
        self._min = min(self._min, val)
        self._stack.append((val, self._min))
    
    def pop(self) -> int:
        val, _ = self._stack.pop()
        self._min = self._stack[-1][1] if self._stack else float('inf')
        return val
    
    def top(self) -> int:
        return self._stack[-1][0]
    
    def get_min(self) -> int:
        return self._stack[-1][1]

7.6.2 表达式语法分析

from typing import Union, List, Dict

class ExpressionEvaluator:
    """
    完整的表达式求值器
    
    支持：
    - 四则运算
    - 括号
    - 幂运算
    - 负号
    - 函数调用
    """
    
    def __init__(self):
        self.precedence = {
            '+': 1, '-': 1,
            '*': 2, '/': 2,
            '^': 3,
            'unary-': 4
        }
        self.right_associative = {'^', 'unary-'}
    
    def tokenize(self, expression: str) -> List[str]:
        """词法分析"""
        tokens = []
        i = 0
        
        while i < len(expression):
            char = expression[i]
            
            if char.isspace():
                i += 1
                continue
            
            if char.isdigit() or char == '.':
                j = i
                while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                    j += 1
                tokens.append(expression[i:j])
                i = j
            elif char.isalpha():
                j = i
                while j < len(expression) and expression[j].isalnum():
                    j += 1
                tokens.append(expression[i:j])
                i = j
            else:
                tokens.append(char)
                i += 1
        
        return tokens
    
    def to_postfix(self, tokens: List[str]) -> List[str]:
        """转换为后缀表达式"""
        output = []
        operators = []
        
        prev_token = None
        
        for token in tokens:
            if token[0].isdigit() or token[0] == '.':
                output.append(token)
            elif token == '(':
                operators.append(token)
            elif token == ')':
                while operators and operators[-1] != '(':
                    output.append(operators.pop())
                operators.pop()
            elif token in '+-*/^':
                op = 'unary-' if token == '-' and (prev_token is None or prev_token in '(+-*/^') else token
                
                while (operators and operators[-1] != '(' and
                       (self.precedence.get(operators[-1], 0) > self.precedence.get(op, 0) or
                        (self.precedence.get(operators[-1], 0) == self.precedence.get(op, 0) and
                         op not in self.right_associative))):
                    output.append(operators.pop())
                operators.append(op)
            
            prev_token = token
        
        while operators:
            output.append(operators.pop())
        
        return output
    
    def evaluate(self, expression: str) -> float:
        """计算表达式"""
        tokens = self.tokenize(expression)
        postfix = self.to_postfix(tokens)
        
        stack: List[float] = []
        
        for token in postfix:
            if token[0].isdigit() or token[0] == '.':
                stack.append(float(token))
            elif token == 'unary-':
                stack.append(-stack.pop())
            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)
                elif token == '^':
                    stack.append(a ** b)
        
        return stack[0]


def demonstrate_expression_evaluator():
    """演示表达式求值"""
    evaluator = ExpressionEvaluator()
    
    expressions = [
        "3 + 4 * 2",
        "(3 + 4) * 2",
        "2 ^ 3 ^ 2",
        "-3 + 4",
        "2 * -3",
    ]
    
    for expr in expressions:
        result = evaluator.evaluate(expr)
        print(f"{expr} = {result}")


if __name__ == '__main__':
    demonstrate_expression_evaluator()

---

7.7 本章小结

7.7.1 核心定理总结

定理	内容	应用
定理 7.1	栈ADT一致性	形式化验证
定理 7.6	表达式等价性	编译原理
定理 7.9	单调栈线性复杂度	算法优化
定理 7.12	递归与栈等价性	递归消除
定理 7.13	尾递归优化	性能优化

7.7.2 时间复杂度汇总

操作	数组实现	链表实现
push	$O(1)$ 均摊	$O(1)$
pop	$O(1)$	$O(1)$
top	$O(1)$	$O(1)$
isEmpty	$O(1)$	$O(1)$

7.7.3 应用场景

应用	算法	复杂度
括号匹配	栈扫描	$O(n)$
表达式求值	Shunting-yard	$O(n)$
下一个更大元素	单调栈	$O(n)$
最大矩形	单调栈	$O(n)$
DFS	栈模拟	$O(V+E)$

---

7.8 习题

理论题

1. 证明：栈ADT的公理系统满足完备性。

2. 证明：Shunting-yard算法的正确性。

3. 分析单调栈解决"下一个更小元素"问题的正确性。

4. 证明：任何递归算法都可以用栈转换为迭代算法。

设计题

5. 设计一个支持 $O(1)$ 获取中位数的栈。

6. 实现一个支持撤销/重做的文本编辑器。

实现题

7. 实现一个支持嵌套括号和函数调用的表达式求值器。

8. 实现一个HTML/XML标签匹配检查器。

---

7.9 参考文献

1. Dijkstra, E. W. (1961). Algol 60 translation. ALGOL Bulletin Supplement, 10.

2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. Section 2.2.1: Stacks.

3. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. Chapter 2: A Simple Syntax-Directed Translator.

4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 1.3: Bags, Queues, and Stacks.

5. Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160.

---

下一章：第8章 队列与广度优先搜索理论