Description
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
Example 1:
1 2
| Input: "1 + 1" Output: 2
|
Example 2:
1 2
| Input: " 2-1 + 2 " Output: 3
|
Example 3:
1 2
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { public int calculate(String s) { Stack<Integer> st = new Stack<>(); int res = 0; int number = 0; int sign = 1; for (int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if (Character.isDigit(ch)){ number = number*10 + (int)(ch - '0'); } else if (ch == '+'){ res += sign * number; number = 0; sign = 1; } else if (ch == '-'){ res += sign * number; number = 0; sign = -1; } else if (ch == '('){ st.push(res); st.push(sign); res = 0; sign = 1; } else if (ch == ')'){ res += sign * number; number = 0; res *= st.pop(); res += st.pop(); } } if (number != 0) res += sign * number; return res; } }
|