当前位置:   article > 正文

【LeetCode】基本计算器 II [M](栈)_leetcode 计算器

leetcode 计算器

227. 基本计算器 II - 力扣(LeetCode)

一、题目

给你一个字符串表达式 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 整数

二、代码

  1. class Solution {
  2. public int calculate(String str) {
  3. // 字符串转换为字符数组
  4. char[] s = str.toCharArray();
  5. // 数组长度
  6. int n = s.length;
  7. // 栈
  8. String[] stack = new String[n];
  9. int top = -1;
  10. // 用来收集数字字符串
  11. StringBuilder numStr = new StringBuilder();
  12. // 遍历字符数组,先将所有的乘除运算计算完,只在栈中保留加减法
  13. for (int i = 0; i < n; i++) {
  14. // 只收集非空格字符
  15. if (s[i] != ' ') {
  16. // 如果遍历到的是数字字符,就收集到numStr中
  17. if (s[i] >= '0' && s[i] <= '9') {
  18. numStr.append(s[i]);
  19. // 如果遍历到的是运算符
  20. } else {
  21. // 首先说明数字收集结束了,生成前面收集的数字字符串
  22. String num = numStr.toString();
  23. // 清空StringBuilder
  24. numStr.setLength(0);
  25. // 此时收集到了数字num和运算符s[i],还没有将其加入到栈中,需要先进行一下运算优先级判断
  26. // 如果此时栈中是非空,就说明里面至少有一个数字和一个字符串
  27. // 如果栈是空,说明此时还没有向栈中加入过数据,就直接将收集到的一个数和运算符加入进去
  28. if (top != -1) {
  29. // 如果此时栈顶是乘除,就先从栈中弹出一个运算符和一个数,与当前刚收集到的数先进行运算,然后再将运算结果和当前收集到的运算符s[i]加入栈中
  30. // 先将所有的乘除都计算完
  31. if ("*".equals(stack[top]) || "/".equals(stack[top])) {
  32. // 弹出一个数和一个运算符
  33. int num2 = Integer.valueOf(num);
  34. String operator = stack[top--];
  35. int num1 = Integer.valueOf(stack[top--]);
  36. // 计算乘除法
  37. int res = compute(num1, num2, operator);
  38. // 将计算结果和新收集的运算符加入栈中
  39. stack[++top] = String.valueOf(res);
  40. stack[++top] = String.valueOf(s[i]);
  41. // 进行下一轮循环
  42. continue;
  43. }
  44. }
  45. // 如果不是栈顶不是乘除法,就直接将收集的到数和运算符加入栈中
  46. stack[++top] = num;
  47. stack[++top] = String.valueOf(s[i]);
  48. }
  49. }
  50. }
  51. // 上面循环中最后一次收集到的数据还没来得及加入栈就结束循环了,所以需要将这个数单独加入栈中
  52. String num = numStr.toString();
  53. // 如果栈不为空,说明还有数字和运算符
  54. if (top != -1) {
  55. // 仍然要做优先级判断
  56. if ("*".equals(stack[top]) || "/".equals(stack[top])) {
  57. int num2 = Integer.valueOf(num);
  58. String operator = stack[top--];
  59. int num1 = Integer.valueOf(stack[top--]);
  60. int res = compute(num1, num2, operator);
  61. // 只需要加结果数字即可
  62. stack[++top] = String.valueOf(res);
  63. // 如果栈顶不是乘除,直接将最后的数字加入到栈中即可
  64. } else {
  65. stack[++top] = num;
  66. }
  67. // 如果栈中没有数据,说明给的原始字符串只有一个数字,即num,直接将其加入栈中
  68. } else {
  69. stack[++top] = num;
  70. }
  71. // 至此栈中不会再有乘除号了
  72. // 如果栈中有超过1个数据,就说明栈中还存在加减的式子,需要计算
  73. if (top > 0) {
  74. // 将栈中的加减法计算出来,结果返回
  75. // 栈中数据一定是一个数,一个运算符交替排列的
  76. // 上一轮的计算结果
  77. int num1 = Integer.valueOf(stack[0]);
  78. String operator = stack[1];
  79. // 循环只遍历数字
  80. for (int i = 2; i <= top; i += 2) {
  81. int num2 = Integer.valueOf(stack[i]);
  82. int res = compute(num1, num2, operator);
  83. num1 = res;
  84. // 最后一个数字就不用再加其后面的运算符了,因为后面已经没有数据了
  85. if (i + 1 <= top) {
  86. operator = stack[i + 1];
  87. }
  88. }
  89. // 返回结果
  90. return num1;
  91. }
  92. // 执行到这里说明栈中只有一个数了,两种情况:
  93. // 1、原式子只有乘除法,在一开始的流程中已经将结果算完了放在栈中了,直接返回即可
  94. // 2、给的字符串只有一个数字,这个数字加入到栈中,直接返回
  95. return Integer.valueOf(stack[top]);
  96. }
  97. // 运算方法
  98. public int compute(int num1, int num2, String operator) {
  99. if ("*".equals(operator)) {
  100. return num1 * num2;
  101. } else if ("/".equals(operator)) {
  102. return num1 / num2;
  103. } else if ("+".equals(operator)) {
  104. return num1 + num2;
  105. } else {
  106. return num1 - num2;
  107. }
  108. }
  109. }

三、解题思路 

从零位置开始向右滑动只会有两种情况:

  1. 当前压中的是数字
  2. 当前压中的是运算符号

准备一个栈。指针开始向右移动,指针划过数字就记录下来。滑过运算符就先判断栈顶是否为乘除,如果是乘除就先算乘除,然后再将划过的运算符加入到栈中。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/848221
推荐阅读
相关标签
  

闽ICP备14008679号