LeetCode-227. 基本计算器 II
题目来源
227. 基本计算器 II
题目详情
给你一个字符串表达式 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 整数
题解分析
解法一:单栈
- 本题与传统的算术表达书相比更简单一点,因为这里并没有左右括号,所以可以不必使用两个栈。
- 这里只需要使用一个栈来存储计算结果,当遇到运算符时,可以根据一个前置运算符计算出前面一部分的运算结果,即栈顶与当前元素的运算结果,并将结果重新入栈。
- 本题可以先遍历整个字符串,并根据连续的数字字符累加出一个完整的数字,接着根据遇到的当前字符来重新计算栈顶元素。
class Solution {
public int calculate(String s) {
Deque sta = new LinkedList<>();
int n = s.length();
int num = 0;
char preSign = '+';// 前置运算符
for(int i=0; i
解法二:双栈法
- 类似于逆波兰表达式的求解思路,这里可以使用双栈来帮助解决问题。其中,操作数栈用来存储运算符号,而数值栈用来存储中间计算过程。
- 需要注意的是,我们需要先对字符串进行预处理,也就是删除字符串中原有的空字符,以免循环过程中对这个特殊字符进行额外的处理。
- 此外,为了防止第一个出现的是负数,需要先在数值栈中放置一个0。
- 另外,考虑到有括号的情况,可能出现(-的形式,所以需要对这种情况进行一步额外的处理,即在数值栈中增加一个0,使之转换为(0-的合法形式。
class Solution {
// 操作符优先级
Map map= new HashMap<>(){{
put('+', 1);
put('-', 1);
put('*', 2);
put('/', 2);
put('%', 2);
}};
public int calculate(String s) {
Deque numsta = new LinkedList<>();// 数值栈
Deque opsta = new LinkedList<>();// 操作数栈
s = s.replaceAll(" ", "");// 删除所有空格
int n = s.length();
numsta.offerFirst(0);
for(int i=0; i 0 && s.charAt(i-1) == '(' && (ch == '+' || ch == '-')){
numsta.offerFirst(0);
}
while(!opsta.isEmpty() && opsta.peekFirst() != '('){
char preops = opsta.peekFirst();
System.out.println(preops + ", " + ch);
if(map.getOrDefault(preops, 0) >= map.getOrDefault(ch, 0)){
cal(numsta, opsta);
}else{
break;
}
}
opsta.offerFirst(ch);
}
}
while(!opsta.isEmpty()){
cal(numsta, opsta);
}
return numsta.peekFirst();
}
private void cal(Deque numsta, Deque opsta){
if(numsta.isEmpty() || numsta.size() < 2){
return;
}
if(opsta.isEmpty()){
return;
}
char ops = opsta.pollFirst();
int num2 = numsta.pollFirst();
int num1 = numsta.pollFirst();
int res = 0;
switch(ops){
case '+':
res = num1 + num2;
break;
case '-':
res = num1 - num2;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num1 / num2;
break;
case '%':
res = num1 % num2;
break;
default:
res = 0;
}
numsta.offerFirst(res);
}
}
参考
【宫水三叶】使用「双栈」解决「究极表达式计算」问题