【LeetCode: 227. 基本计算器 II + 栈】
| 🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯
| 🚀 算法题 🚀 |
🚩 题目链接
⛲ 题目描述
给你一个字符串表达式 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 整数
🌟 求解思路&实现代码&运行结果
⚡ 栈
🥦 求解思路
- 题目中给定的字符串中是包含空格的，我们直接全部替换掉，防止影响后续的求解过程；
- 遍历字符串，判断当前的字符是否是数字，如果是，继续后续的判断，将当前的数完整的解析处理啊；
- 如果当前的字符不是数字(碰到括号)，或者是到达了最后一个位置了，此时需要计算结果，判断此时计算结果的符号；
- 如果是+，将该元素加入
- 如果是-，将该元素的负数加入
- 如果是*，此时栈顶弹出的元素 * 当前元素，然后压入栈中
- 如果是/，此时栈顶弹出的元素 / 当前元素，然后压入栈中
- 当前计算结果重新更新为0，并且更新此时的运算符号状态
- 最后，依次弹出栈中的元素，累加得到最终的结果。
- 有了基本的思路，接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new LinkedList<Integer>();
char preSign = '+';
int num = 0;
s = s.replaceAll(" ","");
int n = s.length();
for (int i = 0; i < n; ++i) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) || i == n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num);
}
preSign = s.charAt(i);
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}
🥦 运行结果
💬 共勉
| 最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！ |
原文地址：https://blog.csdn.net/Coder_ljw/article/details/142612102
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！