题目:
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。
示例 1:
输入:s = "3+2*2"
输出:7
示例 2:
输入:s = " 3/2 "
输出:1
示例 3:
输入:s = " 3+5 / 2 "
输出:5
提示:
- 1 <= s.length <= 3 * 105
- s 由整数和算符 ('+', '-', '*', '/') 组成,中间由一些空格隔开
- s 表示一个 有效表达式
- 表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内
- 题目数据保证答案是一个 32-bit 整数
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这道题和224.基本计算器思路一致,利用栈的特点来解决
建立双栈:
- 使用栈nums:来存放操作数;
- 使用栈ops:来存放操作符。
与224题不同的是多了几个操作符,且上一题中操作符的优先级一样,这一题有优先级的差别,就利用哈希表来存储优先级,键为操作符,值为优先级,优先级按照数学运算中操作符的优先级来限定。
将字符串s中的所有空格去掉,并转换成字符数组,从前往后进行遍历,根据当前遇到的字符进行分情况讨论:
- 遇到左括号 (:就将其加入ops中,等待与之匹配的右括号 );
- 遇到右括号 ):当ops中不为空时,还没遇到与之匹配的左括号时,就将已有的nums和ops进行计算,将结果放入nums中,当遇到与之匹配的左括号时,就将左括号弹出;
- 遇到数字时:就将当前连续的整数取出,放入nums中;
- 有新的操作符入栈时,如果ops栈顶操作符优先级 >= 新的操作符的优先级 ,就计算栈内元素,直到操作符为空或者左括号就继续将操作符入栈,后续遍历完s,再进行计算剩下的。
注意点(有一点改变):
1.第一个数可能为负数(-6):这样第一个操作符可能被认为 '减号',计算时没有前面的数与之计算,可以再最开始就加入一个0,变成 0-6这样结果也正好为-6;
2.为了防止括号内出现的首个字符为运算符,当遇到左括号 ( 时,就添加一个0,使之变为 ( 0,其实与224题效果一样,但是我觉得这个更好利于我理解一点。
代码:
1 class Solution { 2 public int calculate(String s) { 3 Deque<Integer> nums = new ArrayDeque<>(); 4 Deque<Character> ops = new ArrayDeque<>(); 5 Map<Character, Integer> map = new HashMap<>(){{ 6 put('+', 1); 7 put('-', 1); 8 put('*', 2); 9 put('/', 2); 10 put('%', 2); 11 put('^', 3); 12 }}; 13 s = s.replaceAll(" ", ""); 14 char[] cs = s.toCharArray(); 15 int n = cs.length; 16 for(int i = 0; i < n; i++){ 17 char c = cs[i]; 18 //当前遇到左括号,就加入操作符栈 19 if(c == '('){ 20 ops.addLast(c); 21 }else if(c == ')'){ 22 //遇到右括号,就计算括号内的数 23 while(!ops.isEmpty()){ 24 if(ops.pollLast() != '('){ 25 calc(nums, ops); 26 }else{ 27 //计算完括号内的数就弹出左括号 28 ops.pollLast(); 29 } 30 } 31 }else{ 32 if(isNum(c)){ 33 int num = 0; 34 int j = i; 35 //取出当前整数 36 while(j < n && isNum(cs[j])){ 37 num = num * 10 + (cs[j++] - '0'); 38 } 39 nums.addLast(num); 40 i = j -1; 41 }else{ 42 //处理遇到左括号时,应该变成(0 43 if(i > 0 && cs[i - 1] == '('){ 44 nums.addLast(0); 45 } 46 //如果当前c是操作符就看当前操作符的优先级是否小于等于栈内的优先级 47 //如果是,才计算栈内的 48 while(!ops.isEmpty() && ops.peekLast() != '('){ 49 char preop = ops.peekLast(); 50 if(map.get(preop) >= map.get(c)){ 51 calc(nums, ops); 52 }else{ 53 break; 54 } 55 } 56 ops.addLast(c); 57 } 58 } 59 } 60 //遍历完后算剩下的所有 61 while(!ops.isEmpty()){ 62 calc(nums, ops); 63 } 64 return nums.peekLast(); 65 } 66 //计算方法 67 void calc(Deque<Integer> nums, Deque<Character> ops){ 68 //如果操作数为空或者长度小于2 69 if(nums.isEmpty() || nums.size() < 2) return; 70 //如果操作符为空 71 if(ops.isEmpty()) return; 72 int b = nums.pollLast(), a = nums.pollLast(); 73 char c = ops.pollLast(); 74 int res = 0; 75 switch (c){ 76 case '+': 77 res = a + b; 78 break; 79 case '-': 80 res = a - b; 81 break; 82 case '*': 83 res = a * b; 84 break; 85 case '/': 86 res = a / b; 87 break; 88 case '%': 89 res = a % b; 90 break; 91 case '^': 92 res = (int) Math.pow(a, b); 93 break; 94 } 95 nums.addLast(res); 96 } 97 //判断是否为数字 98 boolean isNum(char num){ 99 return Character.isDigit(num); 100 } 101 }
小知识:
1.在数学中优先级:与+、-、*、/相比,幂(^)的优先级最高,最先算。
2.java中运算符的优先级: