栈 - 栈的应用 - 表达式求值、括号匹配等

栈 - 栈的应用 - 表达式求值、括号匹配等

一、引言

在计算机科学的世界里，栈（Stack）是一种非常重要且基础的数据结构。它遵循后进先出（Last In First Out，LIFO）的原则，就像一摞盘子，最后放上去的盘子总是最先被拿走。栈的这一特性使得它在许多算法和实际应用中发挥着关键作用，本文将重点探讨栈在表达式求值和括号匹配这两个常见场景中的应用。

二、栈的基本概念回顾

栈是一种线性数据结构，它只允许在一端进行插入（入栈，Push）和删除（出栈，Pop）操作。这一端被称为栈顶，另一端则称为栈底。除了入栈和出栈操作外，栈通常还支持查看栈顶元素（Peek）和判断栈是否为空（IsEmpty）等操作。

下面是一个简单的 Python 代码示例，实现了一个基本的栈类：

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]
    def size(self):
        return len(self.items)

三、栈在表达式求值中的应用

（一）中缀表达式、前缀表达式和后缀表达式

在数学中，我们常见的表达式是中缀表达式，即运算符位于操作数之间，例如 3 + 4 * 2。但在计算机处理表达式时，前缀表达式（运算符在操作数之前，如 + 3 * 4 2）和后缀表达式（运算符在操作数之后，如 3 4 2 * +）更为方便。

（二）中缀表达式转后缀表达式

中缀表达式转后缀表达式可以借助栈来实现，具体步骤如下：

1. 初始化一个空栈用于存储运算符，一个空列表用于存储后缀表达式。
2. 从左到右扫描中缀表达式的每个元素：
   • 如果是操作数，直接添加到后缀表达式列表中。
   • 如果是左括号，将其压入栈中。
   • 如果是右括号，从栈中弹出运算符并添加到后缀表达式列表中，直到遇到左括号，然后将左括号弹出（但不添加到后缀表达式中）。
   • 如果是运算符，比较其与栈顶运算符的优先级：
     • 如果栈为空或栈顶是左括号，直接将该运算符压入栈中。
     • 否则，若该运算符优先级高于栈顶运算符，将其压入栈中；否则，弹出栈顶运算符并添加到后缀表达式列表中，直到满足压栈条件。
3. 扫描结束后，将栈中剩余的运算符依次弹出并添加到后缀表达式列表中。

以下是 Python 代码实现：

def infix_to_postfix(infix_expr):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = Stack()
    postfix_list = []
    token_list = infix_expr.split()
    for token in token_list:
        if token.isdigit():
            postfix_list.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            top_token = stack.pop()
            while top_token!= '(':
                postfix_list.append(top_token)
                top_token = stack.pop()
        else:
            while (not stack.is_empty()) and (stack.peek() in precedence) and (precedence[stack.peek()] >= precedence[token]):
                postfix_list.append(stack.pop())
            stack.push(token)
    while not stack.is_empty():
        postfix_list.append(stack.pop())
    return " ".join(postfix_list)
# 测试
infix_expr = "3 + 4 * 2"
postfix_expr = infix_to_postfix(infix_expr)
print(f"中缀表达式: {infix_expr}")
print(f"后缀表达式: {postfix_expr}")

（三）后缀表达式求值

后缀表达式求值同样可以使用栈来完成，具体步骤如下：

1. 初始化一个空栈。
2. 从左到右扫描后缀表达式的每个元素：
   • 如果是操作数，将其压入栈中。
   • 如果是运算符，从栈中弹出两个操作数，进行相应的运算，并将结果压入栈中。
3. 扫描结束后，栈中剩下的唯一元素就是表达式的值。

以下是 Python 代码实现：

def evaluate_postfix(postfix_expr):
    stack = Stack()
    token_list = postfix_expr.split()
    for token in token_list:
        if token.isdigit():
            stack.push(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = do_math(token, operand1, operand2)
            stack.push(result)
    return stack.pop()
def do_math(op, op1, op2):
    if op == '+':
        return op1 + op2
    elif op == '-':
        return op1 - op2
    elif op == '*':
        return op1 * op2
    elif op == '/':
        return op1 / op2
# 测试
postfix_expr = "3 4 2 * +"
result = evaluate_postfix(postfix_expr)
print(f"后缀表达式 {postfix_expr} 的值为: {result}")

四、栈在括号匹配中的应用

括号匹配是栈的另一个经典应用场景，在许多编程语言和文本处理中都有重要作用。例如，在编写代码时，编译器需要检查括号是否成对出现，以确保代码的语法正确性。

（一）算法思路

可以使用栈来实现括号匹配，具体步骤如下：

1. 初始化一个空栈。
2. 从左到右扫描字符串：
   • 如果遇到左括号，将其压入栈中。
   • 如果遇到右括号，检查栈是否为空：
     • 如果栈为空，说明右括号没有对应的左括号，返回 False。
     • 否则，弹出栈顶元素，检查弹出的左括号与当前右括号是否匹配：
       • 如果不匹配，返回 False。
3. 扫描结束后，检查栈是否为空：
   • 如果栈为空，说明所有括号都匹配，返回 True。
   • 否则，说明有左括号没有对应的右括号，返回 False。

（二）Python 代码实现

def is_matching_pair(left, right):
    if left == '(' and right == ')':
        return True
    elif left == '[' and right == ']':
        return True
    elif left == '{' and right == '}':
        return True
    return False
def is_balanced(expression):
    stack = Stack()
    for char in expression:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            if stack.is_empty():
                return False
            top = stack.pop()
            if not is_matching_pair(top, char):
                return False
    return stack.is_empty()
# 测试
expression1 = "{[()]}"
expression2 = "{[(])}"
print(f"表达式 {expression1} 是否括号匹配: {is_balanced(expression1)}")
print(f"表达式 {expression2} 是否括号匹配: {is_balanced(expression2)}")

五、总结

栈作为一种简单而强大的数据结构，在表达式求值和括号匹配等场景中发挥了重要作用。通过合理运用栈的后进先出特性，我们可以解决许多实际问题，提高算法的效率和代码的可读性。希望本文能帮助你更好地理解栈的应用，在编程实践中灵活运用这一数据结构。