Problem
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
1 | Example 1: |
Solution
Analysis
数值计算.题目说明,字符串中包括0-9数字,+,-,*,/,以及空格’ ‘, 不包含字母以及括号. 一种方法,可以将字符串转换成逆波兰表达式,然后再计算. 另一种方法是使用栈,直接计算.但是这里还设计到运算符优先级的问题.
这里使用一个栈结构,存入数字,同时,把”+”和”-“纳入数字中,”-“,相当于加上”-num”; 同时注意,数字并不一定是0-9范围内,可能是2位数或更高; 另外, 需要确定什么时候对数字进行计算. 设计到优先级的问题. 比较上一个运算符和当前运算符之间的优先级,如果上一个运算符是”+”或者”-“, 将这个数字(两个运算符之间的数字,也就是上一个运算符针对的这个数字), 然后更新运算符; 如果上一个运算符是”*”或者”/“, 需要从数字栈中弹出一个数字,和当前数字,根据上一个运算进行运算,然后把运算结果压入数据栈, 更新运算符.
最后数据栈中,对应的运算都是+加法运算,依次弹出,直到数据栈为空,返回计算结果.
Code
1 | class Solution { |