这道题类似于一般计算式解答，可以用栈解决，优化的时候可以利用题目本身的特殊性。
原题
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 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/
分享到:
閱讀更多 健程之道 的文章
