每日一题:LeetCode-227. 基本计算器 II
刷题使我快乐,满脸开心.jpg
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1]
的范围内。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval()
。
示例 1:
示例 2:
示例 3:
提示:
1 <= s.length <= 3 * 10^5
s
由整数和算符('+', '-', '*', '/')
组成,中间由一些空格隔开s
表示一个 有效表达式表达式中的所有整数都是非负整数,且在范围
[0, 2^31 - 1]
内题目数据保证答案是一个
32-bit
整数
思路
递归
最开始是想用递归来写的,但是发现递归实现比较复杂,而且实现出来之后数据太难看了,所以换用其他方式
栈
其实栈思路一开始就有,但是个人栈思路的题做的少,第一时间没有选择这个关键就在于拆分元素
和针对符号执行相应动作
:
数字,可能多位,需要组合
空格,直接跳过
+
、-
需要将 数字/数字的负数 压入栈中,等待后续计算,因为有运算优先级存在,所以不能直接处理+
、-
算式,需要先保留*
、/
可以直接跟栈顶的数字进行计算特殊情况 1 第一个数字:因为第一个数字前不会出现符号,下一个符号出来时又其实代表的是下一个数字的行为,所以需要先预设一个
+
操作,然后让符号的动作滞后
一个数字执行特殊情况 2 最后一个数字:最后一个数字解析出来后,并不会有下一个符号出现了,所以很可能出现
无法进入处理
的情况,所以需要增加一个最后一个字符
等条件,保证处理上最后一个数字。
剩下的就简单了。老样子,细节在代码注释
代码
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/6b9029f6549a96330470a6c74】。文章转载请联系作者。
评论