题目描述（中等难度）
基础计算器，只有加减乘除，正数，整数。
思路分析
224 题 已经介绍了两种通用的计算器的解法，一种是利用后缀表达式，一种是双栈，这里就直接在 224 题 的基础上改了，大家可以先去做一下。
解法一 后缀表达式
150 题 已经写了后缀表达式的求值，这里的话我们主要是写中缀表达式转后缀表达式，下边是规则。
1）如果遇到操作数，我们就直接将其加入到后缀表达式。
2）如果遇到左括号，则我们将其放入到栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符加入到后缀表达式直到遇到左括号为止，接着将左括号弹出，但不加入到结果中。
4）如果遇到其他的操作符，如（“+”， “-”）等，从栈中弹出元素将其加入到后缀表达式，直到栈顶的元素优先级比当前的优先级低（或者遇到左括号或者栈为空）为止。弹出完这些元素后，最后将当前遇到的操作符压入到栈中。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
这道题比较简单，不用考虑括号，只需要判断当前操作符和栈顶操作符的优先级。
//op1 > op2 的时候返回 true, 其他情况都返回 false private boolean compare(String op1, String op2) { if (op1.equals("*") || op1.equals("/")) { return op2.equals("+") || op2.equals("-"); } return false; } 下边是整体的代码，供参考。
public int calculate(String s) { String[] polish = getPolish(s); // 转后缀表达式 return evalRPN(polish); } // 中缀表达式转后缀表达式 private String[] getPolish(String s) { List<String> res = new ArrayList<>(); Stack<String> stack = new Stack<>(); char[] array = s.toCharArray(); int n = array.length; int temp = -1; // 累加数字，-1 表示当前没有数字 for (int i = 0; i < n; i++) { if (array[i] == ' ') { continue; } // 遇到数字 if (isNumber(array[i])) { // 进行数字的累加 if (temp == -1) { temp = array[i] - '0'; } else { temp = temp * 10 + array[i] - '0'; } } else { // 遇到其它操作符，将数字加入到结果中 if (temp != -1) { res.add(temp + ""); temp = -1; } // 遇到操作符将栈中的操作符加入到结果中 while (!stack.isEmpty()) { // 栈顶优先级更低就结束 if (compare(array[i]+"",stack.peek())) { break; } res.add(stack.pop()); } // 当前操作符入栈 stack.push(array[i] + ""); } } // 如果有数字，将数字加入到结果 if (temp != -1) { res.add(temp + ""); } // 栈中的其他元素加入到结果 while (!stack.isEmpty()) { res.add(stack.pop()); } String[] sArray = new String[res.size()]; // List 转为 数组 for (int i = 0; i < res.size(); i++) { sArray[i] = res.get(i); } return sArray; } private boolean compare(String op1, String op2) { if (op1.equals("*") || op1.equals("/")) { return op2.equals("+") || op2.equals("-"); } return false; } // 下边是 150 题的代码，求后缀表达式的值 public int evalRPN(String[] tokens) { Stack<String> stack = new Stack<>(); for (String t : tokens) { if (isOperation(t)) { int a = stringToNumber(stack.pop()); int b = stringToNumber(stack.pop()); int ans = eval(b, a, t.charAt(0)); stack.push(ans + ""); } else { stack.push(t); } } return stringToNumber(stack.pop()); } private int eval(int a, int b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; } return 0; } private int stringToNumber(String s) { int sign = 1; int start = 0; if (s.charAt(0) == '-') { sign = -1; start = 1; } int res = 0; for (int i = start; i < s.length(); i++) { res = res * 10 + s.charAt(i) - '0'; } return res * sign; } private boolean isNumber(char c) { return c >= '0' && c <= '9'; } private boolean isOperation(String t) { return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/"); } 解法二 双栈
规则如下。
- 使用两个栈，
stack0用于存储操作数，stack1用于存储操作符 - 从左往右扫描，遇到操作数入栈
stack0 - 遇到操作符时，如果当前优先级低于或等于栈顶操作符优先级，则从
stack0弹出两个元素，从stack1弹出一个操作符，进行计算，将结果并压入stack0，继续与栈顶操作符的比较优先级。 - 如果遇到操作符高于栈顶操作符优先级，则直接入栈
stack1 - 遇到左括号，直接入栈
stack1。 - 遇到右括号，则从
stack0弹出两个元素，从stack1弹出一个操作符进行计算，并将结果加入到stack0中，重复这步直到遇到左括号
同样的不需要考虑括号，会变得更简单一些。
public int calculate(String s) { char[] array = s.toCharArray(); int n = array.length; Stack<Integer> num = new Stack<>(); Stack<Character> op = new Stack<>(); int temp = -1; for (int i = 0; i < n; i++) { if (array[i] == ' ') { continue; } // 数字进行累加 if (isNumber(array[i])) { if (temp == -1) { temp = array[i] - '0'; } else { temp = temp * 10 + array[i] - '0'; } } else { // 将数字入栈 if (temp != -1) { num.push(temp); temp = -1; } // 遇到操作符 while (!op.isEmpty()) { //遇到更低优先级的话就结束 if (compare(array[i], op.peek())) { break; } // 不停的出栈，进行运算，并将结果再次压入栈中 int num1 = num.pop(); int num2 = num.pop(); num.push(eval(num1, num2, op.pop())); } // 当前运算符入栈 op.push(array[i]); } } if (temp != -1) { num.push(temp); } // 将栈中的其他元素继续运算 while (!op.isEmpty()) { int num1 = num.pop(); int num2 = num.pop(); num.push(eval(num1, num2, op.pop())); } return num.pop(); } private boolean compare(char op1, char op2) { if(op1 == '*' || op1 == '/'){ return op2 == '+' || op2 == '-'; } return false; } private boolean isNumber(char c) { return c >= '0' && c <= '9'; } private int eval(int a, int b, char op) { switch (op) { case '+': return a + b; case '-': return b - a; case '*': return a * b; case '/': return b / a; } return 0; } 和 224 题 一样需要注意减法和除法，由于使用了栈，所以算的时候两个数字要反一下。
解法三
分享一下 这里 的解法，属于专门针对这道题的解法。
把减法、乘法、除法在遍历过程中将结果计算出来，最后将所有结果累加。
public int calculate(String s) { int len; if(s==null || (len = s.length())==0) return 0; Stack<Integer> stack = new Stack<Integer>(); int num = 0; char sign = '+'; for(int i=0;i<len;i++){ if(Character.isDigit(s.charAt(i))){ num = num*10+s.charAt(i)-'0'; } if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1){ 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 = s.charAt(i); num = 0; } } int re = 0; for(int i:stack){ re += i; } return re; } 总
这道题的话只是抽离了计算器的一部分功能，只要学会了通用的方法，很快就能写出来。