栈（Stack）的基本概念

栈是一种重要的数据结构，它具有后进先出（Last In First Out，LIFO）的特点。可以把栈想象成一叠盘子，最后放上去的盘子会最先被拿走。

栈的基本操作

  • 入栈（Push）：将元素添加到栈的顶部。
  • 出栈（Pop）：从栈的顶部移除一个元素。
  • 查看栈顶元素（Peek 或 Top）：获取栈顶元素的值，但不移除它。
  • 判断栈是否为空（IsEmpty）：检查栈中是否有元素。

栈的应用场景

  • 表达式求值：在算术表达式求值中，栈可以用于处理运算符的优先级和括号的匹配。例如，将中缀表达式转换为后缀表达式，然后利用栈进行求值。
  • 函数调用栈：在程序执行过程中，当一个函数调用另一个函数时，当前函数的执行状态会被保存到一个栈中（函数调用栈）。当被调用函数执行完毕后，从栈中恢复上一个函数的执行状态继续执行。
  • 括号匹配：在编译器和文本编辑器中，栈可以用于检查括号是否匹配。例如，在检查一段代码或者一个数学表达式中的括号是否成对出现且匹配正确时。
  • 撤销（Undo）操作：在许多软件应用中，撤销操作可以通过栈来实现。每次执行一个操作，该操作的信息被压入栈中。当需要撤销时，从栈中弹出最近的操作信息并执行撤销动作。

后缀表达式： https://leetcode.cn/problems/8Zf90G/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
OPS = ["+", "-", "*", "/"]

def calc(arg0, op, arg1):
    if op == "+":
        return int(arg0) + int(arg1)
    elif op == "-":
        return int(arg0) - int(arg1)
    elif op == "*":
        return int(arg0) * int(arg1)
    elif op == "/":
        return int(int(arg0) / int(arg1))
    else:
        return None

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in OPS:
                stack.append(token)
            else:
                arg1 = stack.pop()
                arg0 = stack.pop()
                res = calc(arg0, token, arg1)
                stack.append(res)
        return int(stack.pop())