題目來源
224. 基本計算器
題目詳情
給你一個字串運算式 s ，請你實作一個基本計算器來計算并回傳它的值，
注意:不允許使用任何將字串作為數學運算式計算的內置函式，比如 eval() ，
示例 1：
輸入： s = "1 + 1"
輸出： 2
示例 2：
輸入： s = " 2-1 + 2 "
輸出： 3
示例 3：
輸入： s = "(1+(4+5+2)-3)+(6+8)"
輸出： 23
提示：
1 <= s.length <= 3 * 105s由數字、'+'、'-'、'('、')'、和' '組成s表示一個有效的運算式- '+' 不能用作一元運算(例如， "+1" 和
"+(2 + 3)"無效) - '-' 可以用作一元運算(即 "-1" 和
"-(2 + 3)"是有效的) - 輸入中不存在兩個連續的運算子
- 每個數字和運行的計算將適合于一個有符號的 32位 整數
相似題目
LeetCode-227. 基本計算器 II
題解分析
與 LeetCode-227. 基本計算器 II 題目類似，本題也是要求計算一個算術等式，等式中可能包含括號，空格，加減符號以及數字等字符，這類題目比較直觀的解法是使用雙堆疊，其中，一個堆疊專門用于存盤符號，另一個堆疊專門用于存盤數字，
使用雙堆疊法的好處是直觀，易于理解，但是缺點也很明顯，比如需要考慮的分支條件很多，需要列舉的情況也很多，通常使用雙堆疊的解法代碼量較大，而且極易寫錯，
本文中采用的一種解法是單堆疊法，這里的單堆疊其實值得是數值堆疊，也就是只存盤數字，為什么這里可以使用數值堆疊呢？原因是對于這里只包含加減運算子的運算式，完全可以把加減運算子的結果寫入數值堆疊中，換句話說，對于正數，直接往數值堆疊中寫入原值即可，對于負數，則往數值堆疊中寫入負值，在最后計算時，只需要將堆疊中的元素依次相加即可得到運算結果，
然而，本題中的符號不僅包括加減，還包括括號，對于括號中的運算，具備優先一起計算的特點，由于括號的出現，上述單堆疊法似乎行不通了，其實，當仔細觀察帶括號的運算式時，我們可以發現，括號內的運算式完全可以作為一個子運算式進行求解，求解完后再將結果作為外層運算式的運算值，所以，基于上述性質，這里可以使用遞回的思路完成帶括號的運算式運算，也就是每次遇到左括號就呼叫一次遞回函式，遇到右括號就結束遞回，計算堆疊中的結果回傳到外層，外層會將該結果入堆疊，作為中間運算元繼續遍歷原運算式，
需要注意的是，因為引入了遞回，進入遞回后的運算式不能重復計算，所以在函式中需要記錄當前遍歷到的字串位置，遞回回傳到外層時需要從新的位置繼續遍歷，
java代碼實作
class Solution {
// 字串的長度
int n;
// 記錄當前遍歷的位置
int pt;
public int calculate(String s) {
n = s.length();
pt = 0;
return dfs(s, 0);
}
public int dfs(String s, int i) {
Deque<Integer> sta = new LinkedList<>();
int num = 0;
char sign = '+';
while (i<n) {
char ch = s.charAt(i++);
pt = i;
if (Character.isDigit(ch)) {
num = num * 10 + ch - '0';
}
if (ch == '(') {
num = dfs(s, i);
i = pt;
}
// 當前字符為左括號，也會將計算好的括號內的數字進堆疊
if ((!Character.isDigit(ch) && ch != ' ') || (i == n)) {
switch (sign) {
case '+':
sta.push(num);
break;
case '-':
sta.push(-num);
break;
}
num = 0;
sign = ch;
}
// 當前為右括號，也將右括號前的數字進堆疊了
if (ch == ')') {
break;
}
}
int res = 0;
while(!sta.isEmpty()) {
res += sta.pop();
}
return res;
}
}
思考
雖然上述代碼中只考慮了加減運算子，但是由此可以將其擴展到同時包含乘除運算子的運算式求解中，在包含乘除符號時，代碼的實作邏輯是很像的，只不過在將數值入堆疊時，因為乘除的運算優先級大于加減，所以需要將前一個元素出堆疊并與當前元素運算后再進堆疊，這樣做，可以保證乘除的優先級更高，
Either Excellent or Rusty轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540859.html
標籤：Java
下一篇：Generator(生成器),入門扯訓,Coroutine(原生協程),登峰造極,Python3.10并發異步編程async底層實作