227. 基本计算器 II

题目

你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：

  1. 输入：s = "3+2*2"
  2. 输出：7

示例 2：

  1. 输入：s = " 3/2 "
  2. 输出：1

示例 3：

  1. 输入：s = " 3+5 / 2 "
  2. 输出：5

提示：

  • 1 <= s.length <= 3 * 10^5
  • s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

**

题解

大晚上的，看题不仔细，还以为表达式中会出现括号()，写得欲仙欲死，一度怀疑这是不是中等题。
后来发现不用考虑括号的情况，那就简单了。

思路1

最简单的方法，就是先用 '+' 将字符串分割成多个多项式，再用 '-' 进行分割，这样剩下的表达式中就只剩下数字和乘除'*', '/'了，这样就很好解决了。

def cal(S):
    num = 0
    res = 1
    opt = '*'
    for i in S:
        if i.isdigit():
            num = num*10+int(i)
        elif i == '*' or i == '/':
            res = res*num if opt == '*' else res//num
            num, opt = 0, i
    res = res*num if opt == '*' else res//num
    return res


def cal2(s):
    L = s.split('+')
    res = 0
    for S in L:
        L_s = S.split('-')
        for i in range(len(L_s)):
            res=res+cal(L_s[i]) if i==0 else res-cal(L_s[i])
    return res

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ", "")
        return cal2(s)

思路2

用栈来解决，流程如下： 227. 基本计算器 II - 图1代码实现的时候，读入最后一个数字后程序会终止，可以通过在字符串末尾加入一个伪节点避免。

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ", "")+'@'
        L = []
        opt = '+'
        num = 0
        for i in s:
            if i.isdigit():
                num = num*10+int(i)
                continue
            elif opt== '*' or opt== '/':
                L[-1] = L[-1]*num if opt== '*' else int(L[-1]/num)
            elif opt == '+' or opt == '-':
                L.append(num if opt =='+' else -1*num)
            num=0
            opt=i
        return sum(L)

image.png