问题描述
LeetCode 227. 基本计算器 II (opens in a new tab)，难度中等。
给你一个字符串表达式 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 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
题解
栈
解题思路：创建一个栈用于保存操作数。遍历字符串，如果当前字符是“ +- 运算符”，则压入栈中；如果当前字符是“ */ 运算符”，则从栈中取数计算后重新压入栈中。最后将栈中的数据累加。
为什么运算符是后更新？ 这是因为我们需要在处理当前数字和前一个运算符之后再更新运算符，以确保当前数字被正确处理。
Solution.java
class Solution {
public int calculate(String s) {
if (s.isEmpty()) return 0;
Stack<Integer> stack = new Stack<>();
int result = 0;
// 当前数字
int num = 0;
char sign = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
// 判断并计算出数字
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
switch (sign) {
case '+':
// 将当前数字压入栈
stack.push(num);
break;
case '-':
// 将当前数字的相反数压入栈
stack.push(-num);
break;
case '*':
// 弹出栈顶元素，与当前数字相乘后压入栈
stack.push(stack.pop() * num);
break;
case '/':
// 弹出栈顶元素，与当前数字相除后压入栈
stack.push(stack.pop() / num);
break;
}
// 更新运算符
sign = c;
num = 0;
}
}
// 将栈内数据累加
for (int i : stack) {
result += i;
}
return result;
}
}