题目来源
题目详情
给你一个字符串表达式 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<Integer> sta = new LinkedList<>();
int n = s.length();
int num = 0;
char preSign = '+';// 前置运算符
for(int i=0; i<n; i++){
char ch = s.charAt(i);
if(Character.isDigit(ch)){
num = num * 10 + ch - '0';
}
// 遇到最后一个字符或者遇到运算符，则计算栈顶
if(i == n-1 || (!Character.isDigit(ch) && ch != ' ')){
switch(preSign){
case '+':
sta.push(num);
break;
case '-':
sta.push(-num);
break;
case '*':
sta.push(sta.pollFirst() * num);
break;
default:
sta.push(sta.pollFirst() / num);
}
num = 0;
preSign = ch;
}
}
int res = 0;
while(!sta.isEmpty()){
res += sta.pollFirst();
}
return res;
}
}
解法二：双栈法
- 类似于逆波兰表达式的求解思路，这里可以使用双栈来帮助解决问题。其中，操作数栈用来存储运算符号，而数值栈用来存储中间计算过程。
- 需要注意的是，我们需要先对字符串进行预处理，也就是删除字符串中原有的空字符，以免循环过程中对这个特殊字符进行额外的处理。
- 此外，为了防止第一个出现的是负数，需要先在数值栈中放置一个0。
- 另外，考虑到有括号的情况，可能出现(-的形式，所以需要对这种情况进行一步额外的处理，即在数值栈中增加一个0，使之转换为(0-的合法形式。
class Solution {
// 操作符优先级
Map<Character, Integer> map= new HashMap<>(){{
put('+', 1);
put('-', 1);
put('*', 2);
put('/', 2);
put('%', 2);
}};
public int calculate(String s) {
Deque<Integer> numsta = new LinkedList<>();// 数值栈
Deque<Character> opsta = new LinkedList<>();// 操作数栈
s = s.replaceAll(" ", "");// 删除所有空格
int n = s.length();
numsta.offerFirst(0);
for(int i=0; i<n; i++){
char ch = s.charAt(i);
if(ch == '('){
opsta.offerFirst(ch);
}else if(ch == ')'){// 遇到右括号则一直进行计算，直到遇到左括号
while(!opsta.isEmpty()){
if(opsta.peekFirst() != '('){
cal(numsta, opsta);
}else{
opsta.pollFirst();// 出栈左括号
break;
}
}
}else if(Character.isDigit(ch)){
int num = 0;
for(; i<n && Character.isDigit(s.charAt(i)); i++){
num = num * 10 + s.charAt(i) - '0';
}
i--;
numsta.offerFirst(num);
}else{// 遇到操作符，则计算栈中优先级高于当前运算符之间的元素
if(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<Integer> numsta, Deque<Character> 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);
}
}