中缀表达式转后缀表达式（逆波兰表达式）并进行计算

最近准备找实习，记录一下算法类刷题的题目

表达式的计算是栈的经典题目，记录一下中缀表达式转后缀表达式的算法思想，代码，以及例子。

中缀表达式：(2*(3-4))*5
后缀表达式：2 3 4 - * 5 *

转换过程需要用到栈，具体过程如下：

（1）如果遇到操作数，我们就直接将其输出。

（2）如果遇到操作符，首先判断是不是“（”，如果是，则直接放入栈中，如果是其他操作符，如“+”，“-”，“*”，“/”则需要查看栈顶元素。

        1）如果当前操作符的优先级小于等于栈顶元素，且栈非空，且栈顶不为“(” ：则将栈顶元素出栈，直到遇到“（”或者，优先级高于当前元素的栈内元素

        2) 其他情况直接将操作符压入栈

（3）如果遇到“）” 则直接将栈内元素出栈，直到遇到“（”，左括号出栈，但不输出到后缀表达式

（4）最后，如果还有未处理完的字符直接加入后缀表达式，栈内元素也依次出栈加入后缀表达式

一个例子如下：

实现代码如下：

def infix_to_postfix(expression):
    # 定义运算符优先级
    precedence = {
        '+': 1,
        '-': 1,
        '*': 2,
        '/': 2,
    }

    # 初始化栈和后缀表达式列表
    operator_stack = []
    postfix = []

    # 当前正在处理的数字
    current_number = ''

    # 遍历表达式
    for char in expression:
        if char.isdigit():  # 如果是数字，继续拼接
            current_number += char
        else:
            # 如果当前字符不是数字，且有正在处理的数字，则将数字添加到后缀表达式
            if current_number:
                postfix.append(current_number)
                current_number = ''

            if char in precedence:  # 如果是运算符
                # 弹出优先级高于或等于当前运算符的栈顶运算符
                while (operator_stack and operator_stack[-1] != '(' and
                       precedence.get(operator_stack[-1], 0) >= precedence[char]):
                    postfix.append(operator_stack.pop())
                operator_stack.append(char)  # 当前运算符入栈
            elif char == '(':  # 如果是左括号，直接入栈
                operator_stack.append(char)
            elif char == ')':  # 如果是右括号
                # 弹出栈顶运算符直到遇到左括号
                while operator_stack and operator_stack[-1] != '(':
                    postfix.append(operator_stack.pop())
                operator_stack.pop()  # 弹出左括号，但不加入后缀表达式
            else:
                raise ValueError(f"Invalid character: {char}")

    # 如果最后还有数字未处理，加入后缀表达式
    if current_number:
        postfix.append(current_number)

    # 将栈中剩余的运算符加入后缀表达式
    while operator_stack:
        postfix.append(operator_stack.pop())

    return postfix


# 示例
expression = "(2*(30-4))*5"
postfix_expression = infix_to_postfix(expression)
print(f"Infix: {expression}")
print(f"Postfix: {postfix_expression}")

得到了后缀表达式，就可以用栈直接计算表达式的值了

class Solution:
    def solve(self , s: str) -> int:
        postfix = infix_to_postfix(s)
        number = []
        operator = []
        n=len(postfix)
        for i in range(n):
            if postfix[i] not in ['+','-','*']:
                number.append(int(postfix[i]))
            elif postfix[i]=='+':
                a=number.pop()
                b=number.pop()
                res = int(a+b)
                number.append(res)
            elif postfix[i]=='-':
                a=number.pop()
                b=number.pop()
                res = int(b-a)
                number.append(res)
            elif postfix[i]=='*':
                a=number.pop()
                b=number.pop()
                res = int(a*b)
                number.append(res)
        final_res = number.pop()
        return final_res