《簡單計算器》在Leetcode中難度為hard浦译，看起來很簡單棒假，里面涉及很多狀態(tài)記錄和匯總，真正做出來還是花了一些時間
1精盅，問題
原題鏈接 https://leetcode.com/problems/basic-calculator/description/
- 實現(xiàn)一個計算器來計算一個簡單表達式帽哑。表達式中可以包含，左括號叹俏，右括號妻枕，加號，減號粘驰，數(shù)字或者空格
例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屡谐，分析
- 看到問題我首先想到遞歸，依次深入蝌数，最后從最小的計算單位算起愕掏。思路沒問題，但效率肯定不高顶伞。
- 如果要效率最高饵撑，最好的算法一定是只經(jīng)過一次遍歷就可以得出結(jié)果剑梳，所以我開始從這個思路下手。
- 這個問題可以分解為對每個數(shù)字進行加減法肄梨，沒有括號的情況很簡單阻荒。
- 有括號的情況，特別是嵌套的時候众羡，括號里的數(shù)字應(yīng)該做加法還是減法侨赡，需要考慮之前的操作符號。
- 比如例3中 "(3-(2-(5-(9-(4)))))"粱侣， 數(shù)字5羊壹， 因為前面2個括號前都是負號，所以對數(shù)字5應(yīng)該做加法
3齐婴，算法
初始化油猫，默認最近的計算符為加號
-
遍歷表達式中的字符
- 如果字符為數(shù)字，獲取整個數(shù)字串轉(zhuǎn)化為數(shù)字
- 根據(jù)最近的計算符累加
- 如果字符為：左括號
- 括號前的操作符入棧
- 計算出棧中所有操作符累計結(jié)果
- 設(shè)置最近的計算符為加號
- 如果字符為：加號
- 設(shè)置最近的計算符為加號
- 如果字符為：減號
- 設(shè)置最近的計算符為負號
- 如果字符為：右括號
- 設(shè)置最近的計算符為加號
- 括號前的操作符出棧
- 如果字符為數(shù)字，獲取整個數(shù)字串轉(zhuǎn)化為數(shù)字
返回最終結(jié)果
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))) {
// 獲得整個數(shù)字
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++;
}
// 根據(jù)最近的操作符累加
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;
}
