版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434778
算法细节系列（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是不是符合这种就近操作？
代码如下：
代码语言：javascript复制 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中有更聪明的做法，用到了些基本性质做了优化，可以提提。
代码语言：javascript复制比如计算： 2 3*2/4 5-2*2
我的做法就不提了，看代码都能明白。
短码的做法：
a. 对字符做了一次预处理，操作如下：
2 3*2/4 5-2*2#
注意字符前的" "和字符后的"#"
b. 对减法的优化：减法就是特殊的加法，操作如下：
2 3*2/4 5 (-2)*2#
就这两步优化，可以为我们省去很多很多代码！
具体操作来看代码吧，有了上述的铺垫，代码就很容易写出来了。代码如下：
代码语言：javascript复制 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
思路：
其实没什么，思路题目已经给你了，还是个就近操作，不过因为加减乘除在这种表达式中无优先级，所以遇到符号就进行计算即可。
代码如下：
代码语言：javascript复制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把字符暂存起来，因为我们实在没有足够的信息去计算。那么一旦遇到右括号，就可以利用第一题的计算方法算出表达式的值，拼接下做后续操作即可。
代码如下：
代码语言：javascript复制 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出，在此基础上计算。代码结构和上述代码一致，但代码更加精简，如下：
代码语言：javascript复制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;
}它的思路更加清楚，对只含有加减的字符串计算，我们可以看成如下：
代码语言：javascript复制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时，在末尾再加一个操作符，如下：
代码语言：javascript复制 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
一道回溯题，主要难点在于对*法的处理，如下：
代码语言：javascript复制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;
减号取个反就好了，一个道理。代码如下：
代码语言：javascript复制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);
}
}
}
