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
Note: Do not use the eval built-in
library function.
Subscribe to see which companies asked this question
java code:
public class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int result = 0;
int sign = 1;
int n = s.length();
for(int i=0;i<n;i++) {
char c = s.charAt(i);
if(Character.isDigit(c)) {
int sum = c-'0';
while(i+1<n && Character.isDigit(s.charAt(i+1))) {
sum = 10*sum + s.charAt(i+1)-'0';
i++;
}
result += sign * sum;
} else if(c=='+') {
sign = 1;
} else if(c=='-') {
sign = -1;
} else if(c=='(') {
stack.push(result);
stack.push(sign);
sign = 1;
result = 0;
} else if(c==')') {
result = result * stack.pop() + stack.pop();
}
}
return result;
}
}原文：http://blog.csdn.net/itismelzp/article/details/51594724