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.
Solution:
class Solution { public int calculate(String s) { int result = 0; int num = 0; int sign = 1; Deque<Integer> contextSign = new ArrayDeque<>(); contextSign.push(sign); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - '0'); } else if (c == '+' || c == '-') { result += sign * num; sign = contextSign.peek() * (c == '+' ? 1 : -1); num = 0; } else if (c == '(') { contextSign.push(sign); } else if (c == ')') { contextSign.pop(); } } result += sign * num; return result; } }