【栈】| 力扣高频题: 基本计算器二

本文主要是介绍【栈】| 力扣高频题: 基本计算器二，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🎗️ 主页：小夜时雨
🎗️专栏：算法题
🎗️如何活着，是我找寻的方向

1. 题目解析

题目链接: https://leetcode.cn/problems/basic-calculator-ii/description/ (可点击)

在这里插入图片描述

本道题是栈的经典应用问题：表达式求值问题, 我们依旧是采取栈 + 分类讨论的方式。

解决思路：

利用栈来模拟计算过程，中间用到分类讨论

初始化一个操作符字符为 ‘+’，为了统一操作，想法：把所有处理过的数字，全部放到栈中，而且栈中的数只需要最后相加就是最后答案。
分情况讨论: 遍历字符串，题目中还有空格，遇到空格直接跳过。
遇到操作符，不做其他操作，直接更新操作符变量，遍历下一个。因为我们是遇到数字的时候才会进行计算和入栈。
遇到数字，有可能是一个多位数的数字，所以要先提取出数字。

判断这个数字前的操作符是什么，来进行入栈操作。
是 ‘+’，数字直接入栈即可
是 ‘-’，数字的相反数入栈即可
是 ‘*’，就可以进行计算了，因为这里没有括号，所以乘和除的计算优先级最高，步骤：取出栈顶元素相乘，之后继续放到栈中
是 ‘-’，取出栈顶元素除以数字，之后放到栈中

把栈中处理过的数字出栈进行相加

接下来的代码里还会再次进行强调的，看下面的图更容易理解：

在这里插入图片描述

2. 代码

看下面的代码对照着上面的流程解析可能会更加的清楚。

class Solution {// 练习public int calculate(String s1) {// 利用一个双端队列 deque, 先计算乘除. 或者是 栈 Stack 也是可以的Deque<Integer> stack = new ArrayDeque<>();int n = s1.length(), i = 0;char op = '+'; // 初始化为 + 号, 为了统一操作: 加入第一个数char[] s = s1.toCharArray();while(i < n) {// 1. 碰见空格, 忽略if(s[i] == ' ') i++;// 2. 碰见数字else if (s[i] >= '0' && s[i] <= '9') {// 提取出数字(有可能是两位或者三位数)int tmp = 0;while(i < n && s[i] >= '0' && s[i] <= '9') {tmp = tmp * 10 + s[i] - '0';i++;}// 提取之后, 判断当前数字前面的符号, 根据符号入栈if(op == '+') stack.push(tmp);else if(op == '-') stack.push(-tmp);else if(op == '*') {// stack.peek() * tmp; 泛型是 Integer, 不是引用类型, 所以不能用 peek, 指向的不是同一个地址// 8.25 更新: 感觉上面说的话不对应该,应该是忘记弹出了// 下一个题中的 泛型是 StringBuffer 就可以stack.push( stack.pop() * tmp );} // else stack.peek() / tmp;else stack.push( stack.pop() / tmp );// i 已经执行非数字了, 所以不用 i++ 了// 3. 碰见符号了, 直接更新符号即可     } else {op = s[i];i++;}}// 遍历完之后, 把栈里的元素进行相加int ret = 0;while(!stack.isEmpty()) {ret += stack.pop();}return ret;}
}