这道题类似于一般计算式解答,可以用栈解决,优化的时候可以利用题目本身的特殊性。
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2" 输出: 7
示例 2:
输入: " 3/2 " 输出: 1
示例 3:
输入: " 3+5 / 2 " 输出: 5
说明:
原题url: https://leetcode-cn.com/probl...
这道题第一眼让我想到的,就是利用两个栈存储运算符和数字,遍历的时候先将相应字符入栈,当遇到运算等级高的(比如 、/ 相对于 +、-,等级更高),直接入栈,否则就压出数进行计算。
让我们看看代码:
class Solution { public int calculate(String s) { // 符号栈 Stack<Character> signStack = new Stack<>(); // 数字栈 Stack<Integer> numStack = new Stack<>(); // 用来存储运算符的等级 Map<Character, Integer> 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(); } }
提交成功,但执行用时只战胜了 43.97%
的 java 提交记录,肯定是可以优化的。
上面之所以慢,应该和压栈、入栈有关,因为这就相当于在重复计算,已经遍历过的内容,又重新遍历。那有什么办法可以直接一次性遍历完并结束呢?
题目里说只有 +、-、*、/
四种运算符,如果是 +、-
,是不可以直接计算的,因为有可能下一个运算符是 *、/
,等级高的会优先计算。但如果是 *、/
,就可以直接计算,因为不存在比它们等级更高的了。
那么到底该怎么解决 +、-
的直接计算呢?其实我们可以 +、-
之后的表达式看做一个整体,直到再次遇到 +、-
。针对这个整体,会有2种情况:
*、/
这样就可以保证只需遍历一遍就可以直接计算出答案了。接下来看看代码:
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}; } }
提交OK,执行用时战胜了 96.66%
的 java 提交记录,这样应该也可以了。
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题可以利用栈解答,也可以利用题目本身的特殊性进行更加高效的解答。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道