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
.
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
Solution 1: Use stack
public class Solution {
public int calculate(String s) {
Deque<Integer> stack=new LinkedList<>();
int n=s.length();
int res=0, sign=1;
for (int i=0; i<n; i++) {
if (s.charAt(i)<='9' && s.charAt(i)>='0') {
int j=i, num=0;
while (j<n && s.charAt(j)<='9' && s.charAt(j)>='0') num=num*10+s.charAt(j++)-'0';
res+=sign*num;
i=j-1;
}
else if (s.charAt(i)=='+') sign=1;
else if (s.charAt(i)=='-') sign=-1;
else if (s.charAt(i)=='(') {
stack.push(res);
stack.push(sign);
res=0;
sign=1;
}
else if (s.charAt(i)==')') {
sign=stack.pop();
int pre=stack.pop();
res=pre+sign*res;
}
}
return res;
}
}
没有评论:
发表评论