LC224. Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces ``.
利用栈实现的典型题目，维护两个栈，分别存num和operator，每次遇到一个字符分情况讨论，结果就是最后栈顶的num。
public class Solution {
public int calculate(String s) {
Stack<Character> operator = new Stack<Character>();
Stack<Integer> num = new Stack<Integer>();
char[] arr = s.toCharArray();
int i = 0; // index
while(i < arr.length){
// if space, continue
if(arr[i] == ' ') {
i++;
continue;
}
// if operator
else if(arr[i] == '+' || arr[i] == '-'){
int nex = i+1; // next char
while(arr[nex] == ' ') nex++;
if(arr[nex] == '('){
operator.push(arr[i]);
nex--;
}else if(arr[nex] <= '9' && arr[nex] >= '0'){
int n = 0; // current number
while(nex < arr.length && arr[nex] <= '9' && arr[nex] >= '0'){
n = n*10 + (arr[nex]-'0');
nex++;
}
nex--;
int peek = num.pop() + (arr[i]=='+'?n:-n);
num.push(peek);
}
i = nex + 1;
} // operator
// if num
else if(arr[i] <= '9' && arr[i] >= '0'){
int n = 0; // current number
while(arr[i] <= '9' && arr[i] >= '0'){
n = n*10 + (arr[i]-'0');
i++;
if(i >= arr.length) break;
}
num.push(n);
}
// if (
else if(arr[i] == '('){
operator.push(arr[i]);
i++;
}
else if(arr[i] == ')'){
assert(operator.pop() == '(');
int peek = num.pop();
while(!operator.isEmpty() && operator.peek() != '('){
peek = num.pop() + (operator.pop()=='+'?peek:-peek);
num.push(peek);
}
if(num.isEmpty()) num.push(peek);
i++;
}
} // while
return num.peek();
}
}
Discuss里面有更简洁的写法。总体而言都是利用栈实现并讨论。