题目表述

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

示例

输入:s = "3+2*2"
输出:7
输入:s = " 3/2 "
输出:1
输入:s = " 3+5 / 2 "
输出:5

题解

  1. 利用一个map存储运算符的优先级,维护两个栈,一个存数,一个存操作符
  2. 遍历字符数组,遇到(压栈,遇到)将栈内元素进行计算,知道遇到(
  3. 如果遇到数字,计算数字大小,进行压栈
  4. 如果遇到的是运算符,在入栈前需要将优先级大于等于该运算符的数进行计算,计算完将数压栈
  5. 数字栈栈顶元素即为结果。

Coding

class Solution {
Map<Character,Integer> map = new HashMap<>();
public int calculate(String s) {
if(s == null || s.length() == 0){
return 0;
}
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
map.put('^',3);
s = s.replaceAll(" ","");
char[] arr = s.toCharArray();
int n = arr.length;
Stack<Integer> num = new Stack<>();
Stack<Character> ops = new Stack<>();

for(int i = 0;i < n;i++){
char c = arr[i];
if(c == '('){
ops.push(c);
}else if(c == ')'){
while(!ops.isEmpty()){
if(ops.peek() == '('){
break;
}else{
calc(ops,num);
}
}
}else{
if(isNumber(c)){
int j = i;
int u = 0;
while(j < n && isNumber(arr[j])){
u = u * 10 + (arr[j] - '0');
j++;
}
num.push(u);
i = j - 1;
}else{
while(!ops.isEmpty() && ops.peek() != '('){
char pre = ops.peek();
if(map.get(pre) >= map.get(c)){
calc(ops,num);
}else{
break;
}
}
ops.push(c);
}
}
}

while(!ops.isEmpty()){
calc(ops,num);
}
return num.peek();
}
public boolean isNumber(char c){
return Character.isDigit(c);
}
public void calc(Stack<Character> ops,Stack<Integer> num){
if(num.isEmpty() || num.size() < 2){
return;
}
if(ops.isEmpty()){
return;
}
int ans = 0;
int b = num.pop();
int a = num.pop();
char op = ops.pop();
if(op == '+'){
ans = a + b;
}else if(op == '-'){
ans = a - b;
}else if(op == '*'){
ans = a * b;
}else if(op == '/'){
ans = a / b;
}else{
ans = (int) Math.pow(a,b);
}
num.push(ans);
}

}