0X00 基础知识

后缀表达式的计算

后缀表达式就是这么简单粗暴，碰到一个符号，就从栈中拿出两个数字计算，再重新放入栈中。

from operator import add, sub, mul, truediv

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        ops = {'+': add, '-': sub, '*': mul, '/': truediv}
        nums = []
        for x in tokens:
            if x not in ops: 
                nums.append(int(x))
                continue
            r, l = nums.pop(), nums.pop()
            nums.append(int(ops[x](l, r)))
        
        return nums[0]

中缀表达式转换成后缀表达式

包含：小数、括号、加减乘除、正负号（以及 ------------10 这种情况）

首先我们得了解一下运算符的优先级（括号另外处理）

加减 < 乘除 < 符号

如果我们要记住这个算法，只需要了理解：

有这么一个栈只能严格递增保存符号，一旦有新的符号小于等之前的符号，那么之前的符号就会被 pop 出来，表示这些符号会先执行

看着很难，其实没这么难，耐心一点

772. 基本计算器 III

from operator import add, sub, mul, truediv
pri_map = {
    '+' : 1,
    '-':  1,
    '*': 2,
    '/': 2,
    's+': 3,
    's-': 3
}

def postfix(s):
    ops = []
    ans = []
    i = 0
    while i < len(s):
        c = s[i]
        if c == '(':
            ops.append(c)
        elif c == ')':
            while ops and ops[-1] != '(':
                ans.append(ops.pop())
            ops.pop()
        elif c in pri_map:
            if c in "+-" and (not i or s[i-1] == '(' or s[i-1] in pri_map):
                 c = 's' + c
            else:
                while ops and ops[-1] != '(' and pri_map[ops[-1]] >= pri_map[c]:
                    ans.append(ops.pop())
            ops.append(c)
        elif c.isdigit():
            d = ""
            j = i
            while j < len(s) and (s[j].isdigit() or s[j] == "."):
                d += s[j]
                j += 1
            i = j - 1
            if '.' not in d:
                ans.append(int(d))
            else:
                ans.append(float(d))
        i += 1
    return ans + ops[::-1]

class Solution:
    def calculate(self, s: str) -> int:
        s = "".join(s.split())
        post = postfix(s)
        # print(post)
        ops = {'+': add, '-': sub, '*': mul, '/': truediv}
        ans = []
        for x in post:
            if x not in pri_map:
                ans.append(x)
            else:
                if x in ['s+', 's-']:
                    t = ans.pop()
                    ans.append(t if t =='s+' else -t)
                else:
                    r, l = ans.pop(), ans.pop()
                    ans.append(ops[x](l, r))
        
        return ans[0]