写点什么

每日一题:LeetCode-227. 基本计算器 II

作者:半亩房顶
  • 2024-01-05
    北京
  • 本文字数:1322 字

    阅读完需:约 4 分钟

每日一题:LeetCode-227. 基本计算器 II

刷题使我快乐,满脸开心.jpg


题目

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


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


你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。


注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval()


示例 1:


输入:s = "3+2*2"输出:7
复制代码


示例 2:


输入:s = " 3/2 "输出:1
复制代码


示例 3:


输入:s = " 3+5 / 2 "输出:5
复制代码


提示:


  • 1 <= s.length <= 3 * 10^5

  • s 由整数和算符 ('+', '-', '*', '/') 组成,中间由一些空格隔开

  • s 表示一个 有效表达式

  • 表达式中的所有整数都是非负整数,且在范围 [0, 2^31 - 1]

  • 题目数据保证答案是一个 32-bit 整数

思路

递归

最开始是想用递归来写的,但是发现递归实现比较复杂,而且实现出来之后数据太难看了,所以换用其他方式

其实栈思路一开始就有,但是个人栈思路的题做的少,第一时间没有选择这个关键就在于拆分元素和针对符号执行相应动作:


  • 数字,可能多位,需要组合

  • 空格,直接跳过

  • +- 需要将 数字/数字的负数 压入栈中,等待后续计算,因为有运算优先级存在,所以不能直接处理 +- 算式,需要先保留

  • */ 可以直接跟栈顶的数字进行计算

  • 特殊情况 1 第一个数字:因为第一个数字前不会出现符号,下一个符号出来时又其实代表的是下一个数字的行为,所以需要先预设一个+操作,然后让符号的动作滞后一个数字执行

  • 特殊情况 2 最后一个数字:最后一个数字解析出来后,并不会有下一个符号出现了,所以很可能出现无法进入处理的情况,所以需要增加一个最后一个字符等条件,保证处理上最后一个数字。


剩下的就简单了。老样子,细节在代码注释

代码

func calculate(s string) int {    sBytes := []byte(s)    // 暂存识别出的数字    num := 0    var stack []int    // 预设一个符号,也就是第一个数字的处理模式    sign := '+'        for i, b := range sBytes {        // 识别数字        if b >= '0' && b <= '9' {            num = num*10 + int(b-'0')        }        // 注意最后一个数字的处理 i == len(sBytes)-1        if ((b > '9' || b < '0') && b != ' ') || i == len(sBytes)-1 {            switch sign {            // 加减不能直接算,这里符号其实是滞后的             // 所以现在的数字其实是符号后的数字,可能会出现后续数字需要优先计算乘除的情况            case '+':                stack = append(stack, num)            case '-':                stack = append(stack, -num)            // 乘除直接算,题目保证算式有效,那就不会出问题            case '*':                stack[len(stack)-1] *= num            case '/':                stack[len(stack)-1] /= num            }            // 符号滞后执行            sign = int32(b)            // 计算后清空缓存的数字            num = 0        }    }
res := 0 for _, i := range stack { res += i } return res}
复制代码




欢迎关注公众号交流更多题目~


发布于: 11 分钟前阅读数: 5
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-227. 基本计算器 II_Go_半亩房顶_InfoQ写作社区