LeetCode 227. 基本计算器 II

227. 基本计算器 II

Difficulty: **   示例 1: 输入:s = "3+22" 输出:7 示例 2: 输入:s = " 3/2 " 输出:1 示例 3: 输入:s = " 3+5 / 2 " 输出:5   提示: 1 <= s.length <= 3 * 105 s 由整数和算符 ('+', '-', '', '/') 组成,中间由一些空格隔开 s 表示一个 有效表达式 表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内 题目数据保证答案是一个 32-bit 整数 **

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

Solution

乘除法运算优先加减运算,可以运用一个栈,提前把乘除法的算完,另外如果是加减法直接带符号放入到栈里面,最后直接对栈里面的数字求和即可。

细节:

在放入栈之前需要考虑元素的前一个符号是什么,这里preSign用于记录元素的前一个符号,比如前一个符号是加减那么直接带符号放入栈里,如果是乘除就要分情况:

  • 乘号:弹出栈顶的元素与当前数字相乘,将相乘的结果放入栈里
  • 除号:题目只要求获得除法运算的整数部分即可,弹出栈顶的元素与当前数字相除取整数部分,结果放入栈里
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        s.replace(' ', '')
        num, preSign = 0, '+'
        for i,v in enumerate(s):
            # 如果i不是运算符,需要先转换为数字,注意'12'这种情况
            if v.isdigit():
                num = num * 10 + ord(v) - ord('0')  # 使用 ASCII 数值计算比int(v)速度更快
            
            if i == len(s) - 1 or v in '+-*/':
                if preSign == '+':
                    stack.append(num)
                elif preSign == '-':
                    stack.append(-num)
                elif preSign == '*':
                    stack.append(stack.pop() * num)
                else:
                    stack.append(int(stack.pop() / num)) # 除法运算只保留整数部分
                preSign = v
                num = 0
        return sum(stack)
上一篇:Openstack 常用命令


下一篇:LeetCode 227. 基本计算器 II