中缀转后缀表达式

中缀转后缀

中缀转后缀表达式

中缀转后缀又叫逆波兰表达式，通过两个栈实现，一个是存储数字，叫数字栈，一个存储符号，叫符号栈

遇到数字直接入数字栈
遇到括号，左括号，直接入符号栈，遇到右括号，符号栈为空直接入栈，从符号栈栈顶弹出运算符入数字栈，直接遇到左括号，左括号对齐
遇到运算符，如果运算符优先级大于栈顶运算符，入符号栈, 反之，将符号栈栈顶弹出运算符，入数字栈，然后再将遇到的运算符入符号栈

def rpn(s):
    oper_stack = Stack()
    num_stack = Stack()

    for i in range(len(s)):
        c = s[i]
        if ord(c) >= 48 and ord(c) <= 57:
            num_stack.push(c)
        elif c == '+' or c == '-':
            if len(oper_stack) > 0 and (oper_stack.peek() == '*' or \
                    oper_stack.peek() == '/'):
                num_stack.push(oper_stack.pop())
            oper_stack.push(c)
        elif c == ')':
            while len(oper_stack) > 0:
                v = oper_stack.pop()
                if v == '(':
                    break
                num_stack.push(v)
        elif c == '(' or c == '*' or c == '/':
            oper_stack.push(c)

    while len(oper_stack) > 0:
        num_stack.push(oper_stack.pop())
    ans = ''

    while len(num_stack) > 0:
        v = num_stack.pop()
        ans += v
    return ans[::-1]

后缀表达式计算

定义一个数字栈，如果是数字则入栈，如果是运算符则弹出栈顶两个元素，进行计算后再入栈，直到最后，然后从栈中弹出计算。

def cal(s):
    num_stack = Stack()
    for i in range(len(s)):
        c = s[i]
        if ord(c) >= 48 and ord(c) <= 57:
            num_stack.push(c)
        else:
            a = num_stack.pop()
            b = num_stack.pop()
            num_stack.push(str(eval(a + c + b)))

    ans = 0
    while len(num_stack) > 0:
        ans += int(num_stack.pop())
    return ans