LeetCode中227. 基本计算器 II题解-java
题目
227. 基本计算器 II
难度中等337
给你一个字符串表达式 s
,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 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) {
// 存储结果
Stack<Integer> numStack = new Stack<>();
// 存储上一操作运算符
char lastOp = '+';
// 将字符串转化为字符数组
char[] arr = s.toCharArray();
// 遍历字符数组
for(int i = 0; i < arr.length; i++){
// 若为空格,则跳过此次循环
if(arr[i] == ' ') continue;
// 若为数字,判断此数字的值,然后判断操作符,与stack的值进行运算,把结果存入stack
if(Character.isDigit(arr[i])){
int tempNum = arr[i] - '0';
while(++i < arr.length && Character.isDigit(arr[i])){
tempNum = tempNum * 10 + (arr[i] - '0');
}
i--;
if(lastOp == '+') numStack.push(tempNum);
else if(lastOp == '-') numStack.push(-tempNum);
else numStack.push(res(lastOp,numStack.pop(), tempNum));
}else if {
// 若为操作符,则将操作符赋予lastOp操作符
lastOp = arr[i];
}
}
int ans = 0;
// 遍历stack栈,遍历加,将结果输出返回
for(int num : numStack) ans += num;
return ans;
}
private int res(char op , int a, int b){
if(op == '*') return a*b;
else if(op == '/') return a/b;
else if(op == '+') return a + b;
else return a - b;
}
}
复杂度分析
提交详情
方法二:栈
思路
代码实现
class Solution {
public int calculate(String s) {
String str = s.replaceAll(" ", "");
Deque<Integer> stack = new LinkedList<Integer>();
char preSign = '+';
int num = 0;
int value = 0;
for(int i = 0; i < str.length(); i++){
if(Character.isDigit(str.charAt(i))){
num = num * 10 + str.charAt(i) - '0';
}
if(!Character.isDigit(str.charAt(i)) || i == str.length() - 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);
break;
}
preSign = str.charAt(i);
num = 0;
}
}
while(!stack.isEmpty()){
value += stack.pop();
}
return value;
}
}