题目描述(中等难度)

227. Basic Calculator II - 图1

基础计算器,只有加减乘除,正数,整数。

思路分析

224 题 已经介绍了两种通用的计算器的解法,一种是利用后缀表达式,一种是双栈,这里就直接在 224 题 的基础上改了,大家可以先去做一下。

解法一 后缀表达式

150 题 已经写了后缀表达式的求值,这里的话我们主要是写中缀表达式转后缀表达式,下边是规则。

1)如果遇到操作数,我们就直接将其加入到后缀表达式。

2)如果遇到左括号,则我们将其放入到栈中。

3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符加入到后缀表达式直到遇到左括号为止,接着将左括号弹出,但不加入到结果中。

4)如果遇到其他的操作符,如(“+”, “-”)等,从栈中弹出元素将其加入到后缀表达式,直到栈顶的元素优先级比当前的优先级低(或者遇到左括号或者栈为空)为止。弹出完这些元素后,最后将当前遇到的操作符压入到栈中。

5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

这道题比较简单,不用考虑括号,只需要判断当前操作符和栈顶操作符的优先级。

  1. //op1 > op2 的时候返回 true, 其他情况都返回 false
  2. private boolean compare(String op1, String op2) {
  3. if (op1.equals("*") || op1.equals("/")) {
  4. return op2.equals("+") || op2.equals("-");
  5. }
  6. return false;
  7. }

下边是整体的代码,供参考。

  1. public int calculate(String s) {
  2. String[] polish = getPolish(s); // 转后缀表达式
  3. return evalRPN(polish);
  4. }
  5. // 中缀表达式转后缀表达式
  6. private String[] getPolish(String s) {
  7. List<String> res = new ArrayList<>();
  8. Stack<String> stack = new Stack<>();
  9. char[] array = s.toCharArray();
  10. int n = array.length;
  11. int temp = -1; // 累加数字,-1 表示当前没有数字
  12. for (int i = 0; i < n; i++) {
  13. if (array[i] == ' ') {
  14. continue;
  15. }
  16. // 遇到数字
  17. if (isNumber(array[i])) {
  18. // 进行数字的累加
  19. if (temp == -1) {
  20. temp = array[i] - '0';
  21. } else {
  22. temp = temp * 10 + array[i] - '0';
  23. }
  24. } else {
  25. // 遇到其它操作符,将数字加入到结果中
  26. if (temp != -1) {
  27. res.add(temp + "");
  28. temp = -1;
  29. }
  30. // 遇到操作符将栈中的操作符加入到结果中
  31. while (!stack.isEmpty()) {
  32. // 栈顶优先级更低就结束
  33. if (compare(array[i]+"",stack.peek())) {
  34. break;
  35. }
  36. res.add(stack.pop());
  37. }
  38. // 当前操作符入栈
  39. stack.push(array[i] + "");
  40. }
  41. }
  42. // 如果有数字,将数字加入到结果
  43. if (temp != -1) {
  44. res.add(temp + "");
  45. }
  46. // 栈中的其他元素加入到结果
  47. while (!stack.isEmpty()) {
  48. res.add(stack.pop());
  49. }
  50. String[] sArray = new String[res.size()];
  51. // List 转为 数组
  52. for (int i = 0; i < res.size(); i++) {
  53. sArray[i] = res.get(i);
  54. }
  55. return sArray;
  56. }
  57. private boolean compare(String op1, String op2) {
  58. if (op1.equals("*") || op1.equals("/")) {
  59. return op2.equals("+") || op2.equals("-");
  60. }
  61. return false;
  62. }
  63. // 下边是 150 题的代码,求后缀表达式的值
  64. public int evalRPN(String[] tokens) {
  65. Stack<String> stack = new Stack<>();
  66. for (String t : tokens) {
  67. if (isOperation(t)) {
  68. int a = stringToNumber(stack.pop());
  69. int b = stringToNumber(stack.pop());
  70. int ans = eval(b, a, t.charAt(0));
  71. stack.push(ans + "");
  72. } else {
  73. stack.push(t);
  74. }
  75. }
  76. return stringToNumber(stack.pop());
  77. }
  78. private int eval(int a, int b, char op) {
  79. switch (op) {
  80. case '+':
  81. return a + b;
  82. case '-':
  83. return a - b;
  84. case '*':
  85. return a * b;
  86. case '/':
  87. return a / b;
  88. }
  89. return 0;
  90. }
  91. private int stringToNumber(String s) {
  92. int sign = 1;
  93. int start = 0;
  94. if (s.charAt(0) == '-') {
  95. sign = -1;
  96. start = 1;
  97. }
  98. int res = 0;
  99. for (int i = start; i < s.length(); i++) {
  100. res = res * 10 + s.charAt(i) - '0';
  101. }
  102. return res * sign;
  103. }
  104. private boolean isNumber(char c) {
  105. return c >= '0' && c <= '9';
  106. }
  107. private boolean isOperation(String t) {
  108. return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/");
  109. }

解法二 双栈

规则如下。

  1. 使用两个栈,stack0 用于存储操作数,stack1 用于存储操作符
  2. 从左往右扫描,遇到操作数入栈 stack0
  3. 遇到操作符时,如果当前优先级低于或等于栈顶操作符优先级,则从 stack0 弹出两个元素,从 stack1 弹出一个操作符,进行计算,将结果并压入stack0,继续与栈顶操作符的比较优先级。
  4. 如果遇到操作符高于栈顶操作符优先级,则直接入栈 stack1
  5. 遇到左括号,直接入栈 stack1
  6. 遇到右括号,则从 stack0 弹出两个元素,从 stack1 弹出一个操作符进行计算,并将结果加入到 stack0 中,重复这步直到遇到左括号

同样的不需要考虑括号,会变得更简单一些。

  1. public int calculate(String s) {
  2. char[] array = s.toCharArray();
  3. int n = array.length;
  4. Stack<Integer> num = new Stack<>();
  5. Stack<Character> op = new Stack<>();
  6. int temp = -1;
  7. for (int i = 0; i < n; i++) {
  8. if (array[i] == ' ') {
  9. continue;
  10. }
  11. // 数字进行累加
  12. if (isNumber(array[i])) {
  13. if (temp == -1) {
  14. temp = array[i] - '0';
  15. } else {
  16. temp = temp * 10 + array[i] - '0';
  17. }
  18. } else {
  19. // 将数字入栈
  20. if (temp != -1) {
  21. num.push(temp);
  22. temp = -1;
  23. }
  24. // 遇到操作符
  25. while (!op.isEmpty()) {
  26. //遇到更低优先级的话就结束
  27. if (compare(array[i], op.peek())) {
  28. break;
  29. }
  30. // 不停的出栈,进行运算,并将结果再次压入栈中
  31. int num1 = num.pop();
  32. int num2 = num.pop();
  33. num.push(eval(num1, num2, op.pop()));
  34. }
  35. // 当前运算符入栈
  36. op.push(array[i]);
  37. }
  38. }
  39. if (temp != -1) {
  40. num.push(temp);
  41. }
  42. // 将栈中的其他元素继续运算
  43. while (!op.isEmpty()) {
  44. int num1 = num.pop();
  45. int num2 = num.pop();
  46. num.push(eval(num1, num2, op.pop()));
  47. }
  48. return num.pop();
  49. }
  50. private boolean compare(char op1, char op2) {
  51. if(op1 == '*' || op1 == '/'){
  52. return op2 == '+' || op2 == '-';
  53. }
  54. return false;
  55. }
  56. private boolean isNumber(char c) {
  57. return c >= '0' && c <= '9';
  58. }
  59. private int eval(int a, int b, char op) {
  60. switch (op) {
  61. case '+':
  62. return a + b;
  63. case '-':
  64. return b - a;
  65. case '*':
  66. return a * b;
  67. case '/':
  68. return b / a;
  69. }
  70. return 0;
  71. }

224 题 一样需要注意减法和除法,由于使用了栈,所以算的时候两个数字要反一下。

解法三

分享一下 这里 的解法,属于专门针对这道题的解法。

把减法、乘法、除法在遍历过程中将结果计算出来,最后将所有结果累加。

  1. public int calculate(String s) {
  2. int len;
  3. if(s==null || (len = s.length())==0) return 0;
  4. Stack<Integer> stack = new Stack<Integer>();
  5. int num = 0;
  6. char sign = '+';
  7. for(int i=0;i<len;i++){
  8. if(Character.isDigit(s.charAt(i))){
  9. num = num*10+s.charAt(i)-'0';
  10. }
  11. if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1){
  12. if(sign=='-'){
  13. stack.push(-num);
  14. }
  15. if(sign=='+'){
  16. stack.push(num);
  17. }
  18. if(sign=='*'){
  19. stack.push(stack.pop()*num);
  20. }
  21. if(sign=='/'){
  22. stack.push(stack.pop()/num);
  23. }
  24. sign = s.charAt(i);
  25. num = 0;
  26. }
  27. }
  28. int re = 0;
  29. for(int i:stack){
  30. re += i;
  31. }
  32. return re;
  33. }

这道题的话只是抽离了计算器的一部分功能,只要学会了通用的方法,很快就能写出来。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情