這道題類似於一般計算式解答，可以用棧解決，優化的時候可以利用題目本身的特殊性。
原題
實現一個基本的計算器來計算一個簡單的字符串表達式的值。
字符串表達式僅包含非負整數，+， - ，*，/ 四種運算符和空格 。 整數除法僅保留整數部分。
示例 1:
<code>輸入: "3+2*2"
輸出: 7
/<code>
示例 2:
<code>輸入: " 3/2 "
輸出: 1
/<code>
示例 3:
<code>輸入: " 3+5 / 2 "
輸出: 5
/<code>
說明：
- 你可以假設所給定的表達式都是有效的。
- 請不要使用內置的庫函數 eval。
原題url：https://leetcode-cn.com/problems/basic-calculator-ii
解答
棧
這道題第一眼讓我想到的，就是利用兩個棧存儲運算符和數字，遍歷的時候先將相應字符入棧，當遇到運算等級高的（比如 、/ 相對於 +、-，等級更高），直接入棧，否則就壓出數進行計算。
讓我們看看代碼：
<code>class Solution {
public int calculate(String s) {
// 符號棧
Stack<character> signStack = new Stack<>();
// 數字棧
Stack<integer> numStack = new Stack<>();
// 用來存儲運算符的等級
Map<character> signLevelMap = new HashMap<>(6);
// +、-是低等級運算符
signLevelMap.put('+', 1);
signLevelMap.put('-', 1);
// *、/是高等級運算符
signLevelMap.put('*', 2);
signLevelMap.put('/', 2);
// 遍歷
int tempNum = 0;
for (char charS : s.toCharArray()) {
// 跳過空格
if (charS == ' ') {
continue;
}
Integer level = signLevelMap.get(charS);
// 如果當前是數字
if (level == null) {
tempNum = charS - '0' + tempNum * 10;
continue;
}
// 如果當前是符號，就把之前的數字壓入numStack
numStack.push(tempNum);
tempNum = 0;
// 如果之前沒有符號，則直接將當前符號壓入棧
if (signStack.empty()) {
signStack.push(charS);
continue;
}
// 如果之前有符號，看看兩者等級
Character signBefore = signStack.peek();
int levelBefore = signLevelMap.get(signBefore);
// 如果當前等級 > 之前的等級
if (level > levelBefore) {
// 將當前符號直接壓入棧
signStack.push(charS);
continue;
}
// 如果當前等級 <= 之前的等級，則可以直接計算之前的符號
while (level <= levelBefore) {
signStack.pop();
int num2 = numStack.pop();
int num1 = numStack.pop();
int result = 0;
switch (signBefore) {
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
}
// 將result再次壓入棧中
numStack.push(result);
if (signStack.empty()) {
break;
}
signBefore = signStack.peek();
levelBefore = signLevelMap.get(signBefore);
}
// 將符號壓入signStack
signStack.push(charS);
}
// 將最後一個數字壓入numStack
numStack.push(tempNum);
// 將棧中所有數據進行計算
int result = 0;
while (!signStack.empty()) {
char sign = signStack.pop();
int num2 = numStack.pop();
int num1 = numStack.pop();
switch (sign) {
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
}
// 將result再次壓入棧中
numStack.push(result);
}
return numStack.pop();
}
}
/<character>/<integer>/<character>/<code>提交成功，但執行用時只戰勝了43.97%的 java 提交記錄，肯定是可以優化的。
結合題目特性
上面之所以慢，應該和壓棧、入棧有關，因為這就相當於在重複計算，已經遍歷過的內容，又重新遍歷。那有什麼辦法可以直接一次性遍歷完並結束呢？
題目裡說只有+、-、*、/四種運算符，如果是+、-，是不可以直接計算的，因為有可能下一個運算符是*、\\，等級高的會優先計算。但如果是*、/，就可以直接計算，因為不存在比它們等級更高的了。
那麼到底該怎麼解決+、-的直接計算呢？其實我們可以+、-之後的表達式看做一個整體，直到再次遇到+、-。針對這個整體，會有2種情況：
- 只是一個數字
- 由*、/連接的表達式，而這種情況其實可以直接計算出結果，這樣也是一個數字了。
這樣就可以保證只需遍歷一遍就可以直接計算出答案了。接下來看看代碼：
<code>class Solution {
public int calculate(String s) {
// 先找到第一個數字
int[] resultArray = findNum(0, s);
int result = resultArray[0];
// 開始遍歷
for (int i = resultArray[1] + 1; i < s.length(); i++) {
char charS = s.charAt(i);
// 空格就跳過
if (charS == ' ') {
continue;
}
// *、/ 就直接計算
if (charS == '*' || charS == '/') {
resultArray = findNum(i + 1, s);
i = resultArray[1];
result = (charS == '*') ? (result * resultArray[0]) : (result / resultArray[0]);
continue;
}
// +、- 就將之後看成一個整體，再計算
if (charS == '+' || charS == '-') {
resultArray = findWholeNum(i + 1, s);
i = resultArray[1];
result = (charS == '+') ? (result + resultArray[0]) : (result - resultArray[0]);
}
}
return result;
}
/**
* 將之後的表達式看成一個整體。
* 返回數組，下標0代表表達式的結果，下標1代表表達式結尾的下標。
*/
public int[] findWholeNum(int index, String s) {
// 找到第一個數
int[] resultArray = findNum(index, s);
int result = resultArray[0];
int newIndex = resultArray[1] + 1;
for (; newIndex < s.length(); newIndex++) {
char charS = s.charAt(newIndex);
if (charS == ' ') {
continue;
}
// 遇到 +、- 就結束
if (charS == '+' || charS == '-') {
break;
}
if (charS == '*' || charS == '/') {
resultArray = findNum(newIndex + 1, s);
newIndex = resultArray[1];
result = (charS == '*') ? (result * resultArray[0]) : (result / resultArray[0]);
}
}
resultArray = new int[]{result, newIndex - 1};
return resultArray;
}
/**
* 找出下一個數字。
* 返回數組，下標0代表數字的值，下標1代表數字結尾的下標。
*/
public int[] findNum(int index, String s) {
int num = 0;
int newIndex = index;
for (; newIndex < s.length(); newIndex++) {
char charS = s.charAt(newIndex);
if (charS == ' ') {
continue;
}
if (charS > '9' || charS < '0') {
break;
}
num = charS - '0' + num * 10;
}
return new int[]{num, newIndex - 1};
}
}
/<code>提交OK，執行用時戰勝了96.66%的 java 提交記錄，這樣應該也可以了。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題可以利用棧解答，也可以利用題目本身的特殊性進行更加高效的解答。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
分享到:
閱讀更多 健程之道 的文章
