LeetCode227 Basic Calculator II 基本计算器

男娘i 2022-05-11 10:28 215阅读 0赞

# 题目描述 #

[Basic Calculator II][]  
给定一些非负整数和符号+, -, \*, /，的组合，中间还有可能有空格。注意整数除法的截断应该往0的方向截断，比如3.5为3，-3.5为-3.  
**样例输入输出**：  
Input: “3+2\*2”  
Output: 7

Input: " 3/2 "  
Output: 1

Input: " 3+5 / 2 "  
Output: 5  
**注意**：  
给定的表达式都是合法的。  
不可以使用内建函数`eval`。

# 思路 #

每当扫描到空格时，continue。  
每当扫描到数字，那么就让存数字的中间变量字符串temp累加当前字符（要用temp时，就使用intv=int(temp)再取出来）。  
每当扫描到一个运算符，那么上一次被扫描的运算符为sign（注意是上一次）。

*  如果sign是+，那么将intv入栈
 *  如果sign是-，那么就-intv入栈
 *  如果sign是\*，那么就将出栈元素乘以intv，再入栈
 *  如果sign是/，那么就将出栈元素除以intv，再入栈（注意取整方向）

注意需要在循环外，再处理一下最后一个数字和最后一个运算符。  
注意特殊情况，表达式只有一个数字，没有符号。

最后，将栈内元素求和，就是结果。

# 代码 #

import math
    
    class Solution:
        def calculate(self, s):
            stack = []
            sign = ''
            temp = ''
            for i in range(len(s)):
                if s[i] == ' ':
                    continue
                if(s[i].isdigit()):#为数字
                    temp += s[i]
                   
                else:#当前为符号时，处理上一个符号
                    intv = int(temp)
                    if sign == '':#第一次读到符号
                        stack.append(intv)#入栈
                    else:
                        if sign == '+':
                            stack.append(intv)
                        elif sign == '-': 
                            stack.append(-intv)
                        elif sign == '*':
                            pop = stack.pop()
                            stack.append(pop*intv)
                        elif sign == '/':
                            pop = stack.pop()
                            stack.append(int(pop/intv))
    
                    sign = s[i]#更新为当前符号
                    temp = ''
            #处理最后一个数字，代码是复制上面来的
            intv = int(temp)
            if sign == '+':
                stack.append(intv)
            elif sign == '-': 
                stack.append(-intv)
            elif sign == '*':
                pop = stack.pop()
                stack.append(pop*intv)
            elif sign == '/':
                pop = stack.pop()
                stack.append(int(pop/intv))
    
            elif sign == '':#如果表达式只有一个数字，没有符号
                return intv
                
            return sum(stack)

多次提交，运行时间不一定，最快时100ms。总结一下就是，每当扫描到运算符，就处理上一个运算符。如果是乘或者除，还需要出栈运算后再入栈，不然就是直接入栈（注意负号）。  
int()函数的取整其实就是往0的方向取整。

# Python3最快代码 #

class Solution:
        def calculate(self, s):
            s += '+'#这样就不用单独处理最后一个数字了
            n = 0
            sign = '+'#也处理了特殊情况，只有一个数字没有运算符
            stk = []
            for c in s:
                if c.isdigit():
                    n = 10 * n + ord(c) - 48
                elif c != ' ':
                    if sign == '+':
                        stk.append(n)
                    elif sign == '-':
                        stk.append(-n)
                    elif sign == '*':
                        stk.append(stk.pop() * n)
                    elif sign == '/':
                        stk.append(int(stk.pop() / n))
                    sign = c
                    n = 0
            return sum(stk)

运行时间68ms。此代码有两个优点，我已经在注释里说了。  
代码思想与我的基本一样，速度方面可能跟这句`n = 10 * n + ord(c) - 48`有关，也许直接操作int变量，比操作字符串变量要快点吧。

[Basic Calculator II]: https://leetcode.com/problems/basic-calculator-ii/description/