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 .
Example 1:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.
class Solution {
public int calculate(String s) {
s = '(' + s + ')';
Stack<String> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
st.push("(");
else if (s.charAt(i) == ')') {
int res = 0;
while (st.size() != 0) {
int x = Integer.parseInt(st.pop());
String second = st.pop();
if (second.compareTo("+") == 0)
res += x;
else if (second.compareTo("-") == 0)
res -= x;
else if (second.compareTo("(") == 0) {
res += x;
break;
}
}
st.push(Integer.toString(res));
} else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
StringBuilder str = new StringBuilder();
while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9')
str.append(s.charAt(i++));
i--;
st.push(str.toString());
} else if (s.charAt(i) == '-' || s.charAt(i) == '+')
st.push(s.charAt(i) + "");
}
return Integer.parseInt(st.pop());
}
}