逆波兰表达式求值&&表达式计算器

1. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

 

示例 1：

输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = [“4”,”13”,”5”,”/“,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22  

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（”+”、”-“、”*” 或 “/“），或是在范围 [-200, 200] 内的一个整数  

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

---

栈

题目限制所有的表达式都是合法的，可以使用栈。
将所有的数字全部入栈，碰到符号时，弹出两个栈顶元素，计算结果后入栈。
注意除法只保留整数部分，对于负数的情况需要特殊处理

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        if len(tokens) == 0:
            return 0
        # 注意一个数的情况
        if len(tokens) == 1:
            return int(tokens[0])
        stack = []
        ops = ['+', '-', '*', '/']
        c = 0
        for token in tokens:
            if token in ops:
                # print(token, stack)
                b = stack.pop()
                a = stack.pop()
                if token == "+":
                    c = a + b
                elif token == "-":
                    c = a - b
                elif token == "*":
                    c = a * b
                else:
                    c = int(a/b)
                stack.append(c)
            else:
                stack.append(int(token))
        return c

2. 表达式计算器的通用套路

能同时解决leetcode 224，227，772

双栈的解法

循环遍历每个元素：
若为空格，跳过
若为左括号，入栈
若为右括号，则计算，直到碰到左括号
若为数字，则入栈
若为符号，则先计算，直到碰到左括号，然后符号入栈

细节需要注意：开头为符号以及括号内开头为符号的情况

class Solution:
    def calculate(self, s: str) -> int:
        def cal(ops, nums):
            if len(ops) == 0:
                return
            while len(ops) > 0 and ops[-1] != '(' and len(nums) >= 2:
                op = ops.pop()
                b = nums.pop()
                a = nums.pop()
                if op == '+':
                    nums.append(a+b)
                if op == '-':
                    nums.append(a-b)
        n = len(s)
        if n == 0:
            return 0
        ops = collections.deque()
        nums = collections.deque()
        # 若开头为符号，加个0方便计算
        if s[0] == '-':
            nums.append(0)
        
        i = 0
        while i < n:
            # print('i', i, '\n')
            e = s[i]
            if e == ' ':
                i += 1
            elif e == '(':
                ops.append(e)
                i += 1
            elif e == '+' or e == '-':
                # 加入符号前，先做判断，将可以计算的部分先计算结果放入nums栈
                cal(ops, nums)
                ops.append(e)
                # 如果左括号内第一个数是符号，那先补0，方便计算
                if i > 0 and s[i-1] == '(':
                    nums.append(0)
                i += 1
            elif e == ')':
                cal(ops, nums)
                op = ops.pop()
                i += 1
            else:
                num = 0
                # print("-----", ops, nums)
                while i < n and '0' <= s[i] and s[i] <= '9':
                    num = 10*num + int(s[i])
                    i += 1
                nums.append(num)
        # 最后可能存在一个括号外的符号和数字需要计算
        cal(ops, nums)
        return sum(nums)

对于+、-、*、/只需要考虑入栈时候的优先级判断即可, 但是代码细节需要做一些微调

class Solution:
    def calculate(self, s: str) -> int:
        def get_priority(op):
            pair = {
                '+': 1,
                '-': 1,
                '*': 2,
                '/': 2
            }
            return pair[op]

        def cal(ops, nums):
            if len(ops) == 0:
                return
            if len(ops) > 0 and ops[-1] != '(' and len(nums) >= 2:
                op = ops.pop()
                b = nums.pop()
                a = nums.pop()
                if op == '+':
                    nums.append(a+b)
                if op == '-':
                    nums.append(a-b)
                if op == '*':
                    nums.append(a*b)
                if op == '/':
                    nums.append(int(a/b))
        n = len(s)
        if n == 0:
            return 0
        ops = []
        nums = []
        # 若开头为符号，加个0方便计算
        if s[0] == '-':
            nums.append(0)
        
        i = 0
        while i < n:
            e = s[i]
            if e == ' ':
                i += 1
            elif e == '(':
                ops.append(e)
                i += 1
            elif e in ['+', '-', '*', '/']:
                # 加入符号前，先做判断，将可以计算的部分先计算结果放入nums栈
                while ops and get_priority(e) <= get_priority(ops[-1]):
                    cal(ops, nums)
                ops.append(e)
                # 如果左括号内第一个数是符号，那先补0，方便计算
                if i > 0 and s[i-1] == '(':
                    nums.append(0)
                i += 1
            elif e == ')':
                while ops and ops[-1] != '(':
                    cal(ops, nums)
                op = ops.pop()
                i += 1
            else:
                num = 0
                # print("-----", ops, nums)
                while i < n and '0' <= s[i] and s[i] <= '9':
                    num = 10*num + int(s[i])
                    i += 1
                nums.append(num)
            # print('i', i, ops, nums)
        # 最后可能存在一个括号外的符号和数字需要计算
        while ops:
            cal(ops, nums)
        return sum(nums)