算法细节系列（25）：加减乘除

详细代码可以fork下Github上leetcode项目，不定期更新。

题目摘自leetcode：

• Leetcode 227. Basic Calculator II
• Leetcode 150. Evaluate Reverse Polish Notation
• Leetcode 224. Basic Calculator
• Leetcode 282. Expression Add Operators

Leetcode 227. Basic Calculator II

思路来源：

• 首先，所有操作符就加减乘除四个符号，优先级就两层，乘除大于加减，所以，解析字符串时，优先计算乘除，加减可以先放一放。（怎么做？栈可以来控制优先级，还有一种技术可以控制优先级计算，递归！但递归说到底就是栈，本质上一样。）
• 栈为什么能控制优先级？想象一下，为什么会有数字存入栈中，无非是因为根据当前信息无法进行计算，为啥？因为加减后可能还有优先级更高的操作，对于加减来说，它们没有选择的余地，只能放在栈中等待着被支配。
• 接着看这道题，如计算2+3*2时，栈中存放了2和3的元素，当遇到乘法2时，它知道了这家伙一定可以被计算，所以再取个2，和3乘得到6。此时表达式就变成了2+6。嘿，好家伙，观察到一个性质没？加减乘除计算都是【就近】找元素来运算的，栈的FILO是不是符合这种就近操作？

代码如下：

 public int calculate(String s) { String ss = s.replace("+","#+").replace("-", "#-").replace("/", "#/").replace("*", "#*"); String[] values = ss.split("#"); int[] nums = new int[values.length]; char[] operators = new char[values.length-1]; int cnt1 = 0; int cnt2 = 0; for (int i = 0; i < values.length; i++){ if (values[i].toCharArray()[0] == '+' || values[i].toCharArray()[0] == '-' || values[i].toCharArray()[0] == '*' || values[i].toCharArray()[0] == '/'){ operators[cnt2++] = values[i].toCharArray()[0]; nums[cnt1++] = Integer.parseInt(values[i].substring(1).trim()); }else{ nums[cnt1++] = Integer.parseInt(values[i].trim()); } } Deque<Integer> numStack = new ArrayDeque<>(); Deque<Character> operatorStack = new ArrayDeque<>(); numStack.push(nums[0]); for (int i = 0; i < operators.length; i++){ if (operators[i] == '*' || operators[i] == '/'){ numStack.push(nums[i+1]); int a1 = numStack.pollFirst(); int a2 = numStack.pollFirst(); switch (operators[i]) { case '*':{ numStack.push(a2 * a1); } break; case '/':{ numStack.push(a2 / a1); } break; default: break; } }else{ operatorStack.push(operators[i]); numStack.push(nums[i+1]); } } while (!operatorStack.isEmpty()){ char opera = operatorStack.pollLast(); int a1 = numStack.pollLast(); int a2 = numStack.pollLast(); switch (opera) { case '+':{ numStack.addLast(a1 + a2);; } break; case '-':{ numStack.addLast(a1 - a2); } break; default: break; } } return numStack.peek(); }

我的代码相对复杂，但就照着上面的思路，慢慢敲就出来，我很多细节没考虑，可以优化的地方太多了，诸如为什么不直接边提取数字和操作符边做计算，起码可以省去一个循环，是吧。用的还不是栈，用的是双端队列，吼吼，计算细节可以慢慢体会。dicuss中有更聪明的做法，用到了些基本性质做了优化，可以提提。

讯享网比如计算： 2+3*2/4+5-2*2 我的做法就不提了，看代码都能明白。 短码的做法： a. 对字符做了一次预处理，操作如下： +2+3*2/4+5-2*2# 注意字符前的"+"和字符后的"#" b. 对减法的优化：减法就是特殊的加法，操作如下： +2+3*2/4+5+(-2)*2# 就这两步优化，可以为我们省去很多很多代码！ 具体操作来看代码吧，有了上述的铺垫，代码就很容易写出来了。

代码如下：

 public int calculate(String s) { if (s == null || s.length() == 0) return 0; char[] cs = s.toCharArray(); Stack<Integer> stack = new Stack<>(); //相当于字符串前的+ char sign = '+'; //开始的数字一定为正 for (int i = 0, num = 0; i < cs.length; i++){ if (Character.isDigit(cs[i])){ num = num * 10 + cs[i] - '0'; } //i == cs.length - 1 相当于那个#，读到#号，还要对最后一个操作符进行计算 if (i == cs.length -1 || !Character.isDigit(cs[i]) && cs[i] != ' '){ //操作符的情况 if (sign == '+'){ stack.push(num); } //减法当+法，省去了加减运算，做后直接遍历加就好了。 if (sign == '-'){ stack.push(-num); } //乘除的就近计算 if (sign == '*'){ stack.push(stack.pop() * num); } if (sign == '/'){ stack.push(stack.pop() / num); } //想想这里，做的其实都是前一步的操作。 sign = cs[i]; num = 0; } } int res = 0; for (int i : stack){ res += i; } return res; }

Leetcode 150. Evaluate Reverse Polish Notation

代码如下：

讯享网

讯享网public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++){ if (!isOperator(tokens[i])){ stack.push(Integer.parseInt(tokens[i])); }else{ int a1 = stack.pop(); int a2 = stack.pop(); if (tokens[i].equals("+")){ stack.push(a2 + a1); } if (tokens[i].equals("-")){ stack.push(a2 - a1); } if (tokens[i].equals("*")){ stack.push(a2 * a1); } if (tokens[i].equals("/")){ stack.push(a2 / a1); } } } return stack.peek(); } private boolean isOperator(String op){ return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/"); }

Leetcode 224. Basic Calculator

先说说我的思路吧：

• 关键问题是右括号，遇到右括号说明表达式闭合，就必须得计算了，所以一旦遇到右括号进行计算。
• 那么遇到左括号怎么办？直接建立一个StringBuilder把字符暂存起来，因为我们实在没有足够的信息去计算。那么一旦遇到右括号，就可以利用第一题的计算方法算出表达式的值，拼接下做后续操作即可。

代码如下：

 public int calculate(String s) { if (s == null || s.length() == 0) return 0; char[] cs = s.toCharArray(); Stack<StringBuilder> stack = new Stack<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < cs.length; i++){ if (cs[i] == '('){ stack.push(sb); sb = new StringBuilder(); } else if (cs[i] == ')'){ int ans = calculateNoparentheses(validExpression(sb.toString())); sb = stack.pop(); sb.append(ans); }else{ sb.append(cs[i]); } } return calculateNoparentheses(validExpression(sb.toString())); } private String validExpression(String s){ return s.replaceAll("-\\s*-", "+").replaceAll("\\+\\s*-", "-"); } //这里还可以优化，其实没必要使用栈 private int calculateNoparentheses(String s){ if (s.length() == 0 || s == null) return 0; Stack<Integer> stack = new Stack<>(); char opera = '+'; char[] cs = s.toCharArray(); for (int i = 0, num = 0; i < s.length(); i++){ if (Character.isDigit(cs[i])){ num = num * 10 + cs[i] - '0'; } if (i == s.length() - 1 || !Character.isDigit(cs[i]) && cs[i] != ' '){ if (opera == '+'){ stack.push(num); } if (opera == '-'){ stack.push(-num); } opera = cs[i]; num = 0; } } int res = 0; for (int num : stack){ res += num; } return res; }

这道题，我们还可以换个角度思考，当没有遇到左括号和右括号，随着遍历的进行，可以直接一步步计算。当遇到左括号就把先前计算的结果存入栈中，再一步步计算，而当遇到右括号，就把栈中的元素poll出，在此基础上计算。代码结构和上述代码一致，但代码更加精简，如下：

讯享网public int calculate(String s) { Stack<Integer> stack = new Stack<>(); char[] cs = s.toCharArray(); int res = 0, sign = 1; int num = 0; for (int i = 0; i < cs.length; i++){ if (Character.isDigit(cs[i])){ num = num * 10 + cs[i] - '0'; } else if (cs[i] == '+'){ res += sign * num; num = 0; sign = 1; } else if (cs[i] == '-'){ res += sign * num; num = 0; sign = -1; } else if (cs[i] == '('){ stack.push(res); stack.push(sign); res = 0; sign = 1; } else if (cs[i] == ')'){ res += sign * num; num = 0; res *= stack.pop(); res += stack.pop(); } } if (num != 0) res += sign * num; return res; }

它的思路更加清楚，对只含有加减的字符串计算，我们可以看成如下：

3+4-4+5-1 +3 +4 -4 +5 -1 上述的遍历方式形象点就是计算： res += (+3); res += (+4); res += (-4); res += (+5); res += (-1); 而当遇到左括号时，需要压入栈的有之前计算的res，以及当前的符号，这样当括号内的表达式计算完毕后，可以在此基础上继续加or减。 还需注意最后的num != 0的情况是因为我们控制算法计算是当遇到下一个操作符，到了字符串末尾自然没有操作符，所以需要额外计算一次。

当然你也可以初始化s时，在末尾再加一个操作符，如下：

讯享网 public int calculate(String s) { Stack<Integer> stack = new Stack<>(); s += "+"; char[] cs = s.toCharArray(); int res = 0, sign = 1; int num = 0; for (int i = 0; i < cs.length; i++){ if (Character.isDigit(cs[i])){ num = num * 10 + cs[i] - '0'; } else if (cs[i] == '+'){ res += sign * num; num = 0; sign = 1; } else if (cs[i] == '-'){ res += sign * num; num = 0; sign = -1; } else if (cs[i] == '('){ stack.push(res); stack.push(sign); res = 0; sign = 1; } else if (cs[i] == ')'){ res += sign * num; num = 0; res *= stack.pop(); res += stack.pop(); } } //if (num != 0) res += sign * num; return res; }

依旧AC。

Leetcode 282. Expression Add Operators

一道回溯题，主要难点在于对*法的处理，如下：

2 + 3 * 5 在递归回溯搜索时，它实际的优先级计算如下： (2 + 3) * 5 而我们要改成：2 + 3 * 5 假设当前val = (2 + 3),且记录右括号左侧第一个数 multed = 3，当前 cur = 5 则：val = val - multed + multed * cur 遇到连乘同样起作用，如： (2 + 3 * 5) * 4 val = 2 + 3 = 5; multed = 3 * 5; cur = 4; 则：val = val - multed + multed * cur; 减号取个反就好了，一个道理。

代码如下：

讯享网public List<String> addOperators(String num, int target) { List<String> rst = new ArrayList<String>(); if(num == null || num.length() == 0) return rst; helper(rst, "", num, 0, target, 0, 0); return rst; } private void helper(List<String> ans, String path, String num, int pos, int target, long val, long multed){ if (pos == num.length()){ if (target == val){ ans.add(path); } } for (int i = pos; i < num.length(); i++){ //排除以0元素开头i结尾的数，如05，00均不合法 if(i != pos && num.charAt(pos) == '0') break; long cur = Long.parseLong(num.substring(pos, i + 1)); // 起初默认的为加法 if (pos == 0){ helper(ans, path + cur, num, i + 1, target, cur, cur); } else{ helper(ans, path + "+" + cur, num, i + 1, target, val + cur, cur); helper(ans, path + "-" + cur, num, i + 1, target, val - cur, -cur); helper(ans, path + "*" + cur, num, i + 1, target, val - multed + multed * cur, multed * cur); } } }