150-逆波兰表达式求值

逆波兰表达式是一种无括号的表达式表示方法，其特点是运算符位于操作数之后。求解逆波兰表达式的方法是使用栈。

1. 初始化一个空栈stack。
2. 从左到右遍历逆波兰表达式的每个元素：
- 如果当前元素是操作数，将其压入栈stack。
- 如果当前元素是操作符：
- 弹出栈顶的两个元素，分别记为a和b。
- 根据当前操作符进行计算，得到结果temp。
- 将temp压入栈stack。
3. 遍历结束后，stack中仅剩一个元素，即为逆波兰表达式的计算结果。

下面是一个使用该算法的Python代码实现：

def evaluate_rpn(expression):
    stack = []
    operators = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: a / b
    }

    for token in expression:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.append(result)
        else:
            stack.append(float(token))  # 将操作数转换为浮点数

    return stack.pop()

expression = ["2", "1", "+", "3", "*"]
result = evaluate_rpn(expression)
print(result)  # 输出：9

以上代码使用字典来存储操作符和对应的函数，利用lambda函数进行计算。在遍历表达式时，如果遇到操作符，则从栈中弹出两个操作数进行计算，并将结果压入栈中；如果遇到操作数，则将其转换为浮点数并压入栈中。遍历结束后，栈中仅剩一个元素，即为逆波兰表达式的计算结果。