191 - 227 基本计算器2

题目

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2" 输出: 7

示例 2:

输入: " 3/2 " 输出: 1

示例 3:

输入: " 3+5 / 2 " 输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。

• 请不要使用内置的库函数 eval。

解答

1是困难，比2需要多判断一下括号的优先级

总感觉这两道题的标号反了。。

只能想到，split字符串，然后取不同的字符串，转换成数字。再相加

https://leetcode.com/problems/basic-calculator-ii/discuss/63076/Python-short-solution-with-stack.

class Solution:
    def calculate(self, s: str) -> int:
        num, stack, sign = 0, [], "+"
        for i in range(len(s)):
            if s[i].isdigit():
                num = num*10 + int(s[i])
            if s[i] in "+-*/" or i == len(s)-1:
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop()*num)
                elif sign == "/":
                    stack.append(int(stack.pop()/num))
                sign, num = s[i], 0
        return sum(stack)

Runtime: 92 ms, faster than 69.86% of Python3 online submissions for Basic Calculator II.

Memory Usage: 14.3 MB, less than 88.89% of Python3 online submissions for Basic Calculator II.

class Solution:
    def calculate(self, s: str) -> int:
        s += "+0"
        stack, num, sign = [], 0, "+"
        for i in range(len(s)):
            if s[i].isdigit():
                num = num*10+int(s[i])
            elif not s[i].isspace():
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop()*num)
                elif sign == "/":
                    stack.append(int(stack.pop()/num))
                sign, num = s[i], 0
        return sum(stack)

Runtime: 72 ms, faster than 92.84% of Python3 online submissions for Basic Calculator II.

Memory Usage: 14.6 MB, less than 88.89% of Python3 online submissions for Basic Calculator II.

split

https://leetcode.com/problems/basic-calculator-ii/discuss/63170/Easy-7-12-lines-Three-solutions

先根据+-拆，然后每个子项根据*/拆

class Solution:
    def calculate(self, s: str) -> int:
        total = 0
        outer = iter(['+']+re.split('([+-])', s))
        for addsub in outer:
            inner = iter(['*'] + re.split('([*/])', next(outer)))
            term = 1
            for muldiv in inner:
                n = int(next(inner))
                term = term*n if muldiv == '*' else term // n
            total += term if addsub == '+' else -term
        return total

Runtime: 148 ms, faster than 21.57% of Python3 online submissions for Basic Calculator II.

Memory Usage: 17.9 MB, less than 7.41% of Python3 online submissions for Basic Calculator II.