Python栈的应用：函数调用、表达式求值、括号匹配

2023-04-10 00:00:00 表达式 匹配 括号
  1. 函数调用：
    在Python中，每个函数调用都会形成一个新的栈帧，存储函数的参数、局部变量和返回地址等信息。函数结束后，栈帧会被弹出，控制权返回到上一个栈帧中。
    例子：
def func1(x):
    y = x + 1
    return y
def func2(a, b):
    c = func1(a) + func1(b)
    return c
result = func2(2, 3)
print(result)

这个程序会输出5，说明func2调用的结果是两个func1调用结果的和。
2. 表达式求值：
表达式求值可以用栈来实现，基本思路是先将中缀表达式转换成后缀表达式（逆波兰表达式），然后使用栈来计算后缀表达式的值。
例子：

def postfix_eval(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = do_math(token, operand1, operand2)
            stack.append(result)
    return stack.pop()
def do_math(operator, operand1, operand2):
    if operator == '+':
        return operand1 + operand2
    elif operator == '-':
        return operand1 - operand2
    elif operator == '*':
        return operand1 * operand2
    elif operator == '/':
        return operand1 / operand2
result = postfix_eval('5 1 2 + 4 * + 3 -')
print(result)

这个程序会输出14，这是后缀表达式计算的结果。
3. 括号匹配：
括号匹配一般也是采用栈来实现。具体做法是遍历字符串，遇到左括号入栈，遇到右括号弹出栈顶元素并比较是否匹配。
例子：

def parentheses_check(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:
                return False
            stack.pop()
    return not stack
string1 = '(pidancode.com)'
string2 = '()(pidancode.com'
string3 = '(pidancode.com))'
string4 = ')pidancode.com('
print(parentheses_check(string1)) # True
print(parentheses_check(string2)) # False
print(parentheses_check(string3)) # False
print(parentheses_check(string4)) # False

这个程序会输出True、False、False、False，这是由于只有string1中的左括号和右括号匹配。

相关文章