224. 基本计算器

Difficulty
Hard
Tags
字符串
URL
https://leetcode-cn.com/problems/basic-calculator/
Star
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
  • 1 <= s.length <= 3 * 105
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式
通过次数75,203提交次数180,142

法1 转后缀表达式求解

思路
先转为后缀表达式，再对后缀表达式求解.
需要注意的是，转为后缀表达式的时候，需要对如下特殊情况 "-2 + 2" 或者 "1-(-2)" 进行特殊处理。处理方式如下：
# 当 负号 前面的左括号 或者 负号为首字符时，在后缀表达式里面加0 
if s[i] == "-" and (i == 0 or s[i-1] == "(" ):
     res.append('0')
题解
class Solution:
    def calculate(self, s: str) -> int:
        
        # 转换为 后缀表达式
        # 运算符优先级
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1

        res = []
        stack = []
        i = 0
        while i < len(s):
            # 数字 直接 接到后缀表达式上
            if s[i] == " ":
                i += 1
                
            elif s[i].isdigit():
                temp = ""
                while i < len(s) and s[i].isdigit():
                    temp += s[i]
                    i += 1
                res.append(temp)

            # 左括号直接入栈
            elif s[i] == "(":
                stack.append(s[i])
                i += 1

            # 右括号，开始弹栈，直达遇到左括号 左括号出栈 但不输出
            elif s[i] == ")":
                while stack and stack[-1] != "(":
                    res.append(stack.pop())
                stack.pop() # 左括号出战， 但是不输出
                i += 1

            # 遇到运算符
            elif s[i] in ["+", "-", "*", "/"]:
                #  对 "-2 + 2" 或者 "1-(-2)" 进行特殊处理
                if s[i] == "-" and (i == 0 or s[i-1] == "(" ):
                    res.append('0')
                # 只要栈顶符号不低于当前符号，就一直输出。最后把当前符号入栈
                while stack and prec[stack[-1]] >= prec[s[i]]:
                    res.append(stack.pop())
                stack.append(s[i])
                i += 1
        
        # 最后把栈里面的元素均 放到后缀表达式后面
        while stack:
            res.append(stack.pop())


        # 计算后缀表达式
        stack = []
        
        for char in res:
            if char.isdigit():
                stack.append(int(char))
            else:
                x = stack.pop()
                y = stack.pop() 
                if char == "+":
                    stack.append(x + y)
                elif char == "-":
                    stack.append(y-x)
                elif char == "*":
                    stack.append(y*x)
                elif char == "/":
                    stack.append(x/y)

        return stack.pop()

法2 双栈

思路
建立两个栈，stack_nums 存放数字，stack_ops存放运算符号。具体的运算规则为：
  1. 数字 直接入 stack_nums 栈
  1. 符号 入 stack_ops，但是 在入栈前，需要先将可以计算的运算符计算完
  1. 左括号 直接入stack_ops 栈
  1. 右括号 则将stack_ops内可以计算的全部计算完成，直至遇到左括号，此时左括号出栈。（注：右括号是不会进栈的）
特殊情况：如-1+3 或者 **(-3+7)** 这种情况，需要转为 0-1+3 和 **(0-3+7)** ， 可以事先遍历一遍，进行转化，也可以 在处理的时候，同时转化。
题解
class Solution:
    def calculate(self, s: str) -> int:
        stack_num = []
        stack_ops = []
        
        i = 0
        while i < len(s):
            if s[i] == " ":
                i += 1
            elif s[i].isdigit():
                temp = []
                while i < len(s) and s[i].isdigit():
                    temp.append(s[i])
                    i += 1
                stack_num.append(int("".join(temp)))
            elif s[i] == "-" or s[i] == "+":
                self._calculate(stack_num, stack_ops)
                stack_ops.append(s[i])
                if i == 0:
                    stack_num.append(0)
                i += 1

            elif s[i] == "(":
                stack_ops.append("(")
                if i + 1 < len(s) and s[i+1] in {"+", "-"}:
                    stack_num.append(0)
                i += 1
            elif s[i] == ")":
                self._calculate(stack_num, stack_ops)
                stack_ops.pop()
                i += 1
        
        self._calculate(stack_num, stack_ops)
        return stack_num.pop()

    def _calculate(self, stack_num, stack_ops):
        while len(stack_ops) > 0 and stack_ops[-1] != "(":
            x = stack_num.pop()
            y = stack_num.pop()
            op = stack_ops.pop()
            z = x + y if op == "+" else y - x
            stack_num.append(z)