《简单计算器》在Leetcode中难度为hard，看起来很简单，里面涉及很多状态记录和汇总，真正做出来还是花了一些时间
1，问题
原题链接 https://leetcode.com/problems/basic-calculator/description/
- 实现一个计算器来计算一个简单表达式。表达式中可以包含，左括号，右括号，加号，减号，数字或者空格
例1
Input: "1 + 1"
Output: 2
例2
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
例3
Input: "(3-(2-(5-(9-(4)))))"
Output: 1
2，分析
- 看到问题我首先想到递归，依次深入，最后从最小的计算单位算起。思路没问题，但效率肯定不高。
- 如果要效率最高，最好的算法一定是只经过一次遍历就可以得出结果，所以我开始从这个思路下手。
- 这个问题可以分解为对每个数字进行加减法，没有括号的情况很简单。
- 有括号的情况，特别是嵌套的时候，括号里的数字应该做加法还是减法，需要考虑之前的操作符号。
- 比如例3中 "(3-(2-(5-(9-(4)))))"， 数字5， 因为前面2个括号前都是负号，所以对数字5应该做加法
3，算法
初始化，默认最近的计算符为加号
-
遍历表达式中的字符
- 如果字符为数字，获取整个数字串转化为数字
- 根据最近的计算符累加
- 如果字符为：左括号
- 括号前的操作符入栈
- 计算出栈中所有操作符累计结果
- 设置最近的计算符为加号
- 如果字符为：加号
- 设置最近的计算符为加号
- 如果字符为：减号
- 设置最近的计算符为负号
- 如果字符为：右括号
- 设置最近的计算符为加号
- 括号前的操作符出栈
- 如果字符为数字，获取整个数字串转化为数字
返回最终结果
4，完整代码
public int calculate(String s) {
// 以下使用boolean类型来表示加加法，true为加法，false为减法
boolean operArr[] = new boolean[s.length()];
boolean finalOperInArr = true;
int operOff = 0;
int ret = 0;
boolean lastOperPlus = true;
for(int i=0; i<s.length(); i ++){
if (Character.isDigit(s.charAt(i))) {
// 获得整个数字
int sum = s.charAt(i) - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
sum = sum * 10 + s.charAt(i + 1) - '0';
i++;
}
// 根据最近的操作符累加
if(lastOperPlus == finalOperInArr)
ret += sum;
else
ret -= sum;
}
if(s.charAt(i)=='('){
// 操作符入栈
operArr[operOff++] = lastOperPlus;
finalOperInArr = finalOperInArr == lastOperPlus;
lastOperPlus = true;
}else if(s.charAt(i) == '+'){
lastOperPlus = true;
}else if(s.charAt(i) == '-') {
lastOperPlus = false;
}else if(s.charAt(i)==')'){
lastOperPlus = true;
// 操作符出栈
finalOperInArr = finalOperInArr == operArr[--operOff];
}
}
return ret;
}
