用栈实现四则运算的笔记

栈是一种先进后出（Last-In-First-Out）的数据结构，可以用来处理四则运算中的表达式。通过将表达式转换为逆波兰表达式，我们可以使用栈来计算表达式的值。

逆波兰表达式是一种无括号的表达式表示方式，其中运算符位于操作数之后，例如“2 3 +”。该表达式的计算方式为从左到右扫描表达式，遇到操作数则将其入栈，遇到运算符则将栈顶的两个操作数弹出并进行该运算符的运算，将结果入栈。最终栈中只剩下一个元素，即为表达式的计算结果。

下面是用栈实现四则运算的基本思路：

1. 从左到右扫描表达式中的每个元素。
2. 如果当前元素是操作数，则将其入栈。
3. 如果当前元素是操作符，则取出栈顶的两个操作数进行运算，并将运算结果入栈。
4. 重复步骤2和3，直到表达式扫描完毕。
5. 最终栈中只剩下一个元素，即为表达式的计算结果。

具体实现时，我们可以使用一个数组模拟栈的操作，定义一个指针top表示栈顶元素的位置，每次入栈操作时将top加1，出栈操作时将top减1。

参考代码如下（以计算逆波兰表达式为例）：

def calculate(expr):
    stack = []
    for token in expr:
        if token.isdigit():
            stack.append(int(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)
    return stack.pop()

其中，expr表示逆波兰表达式，token表示表达式中的每个元素。如果当前元素是数字，则将其转换为整数并入栈；如果是操作符，则从栈中取出两个操作数进行运算，并将运算结果入栈。最终栈中只剩下一个元素，即为表达式的计算结果。

需要注意的是，这里的实现并不支持带括号的表达式，如果需要支持括号，则需要对表达式进行转换，将括号内的表达式转换为逆波兰表达式，并递归地计算表达式的值。