Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
1 2 3
| "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5
|
Note: Do not use the eval built-in library function.
O(n) time O(n) space 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
| public class Solution { public int calculate(String s) { if (s == null || s.length() == 0) return 0; Stack<Integer> stack = new Stack<>(); char sign = '+'; int num = 0; for (int i = 0; i < s.length(); i++) { if (Character.isDigit(s.charAt(i))) { num = num * 10 + s.charAt(i) - '0'; } if ((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == s.length() - 1) { if (sign == '+') { stack.push(num); } else if (sign == '-') { stack.push(-num); } else if (sign == '*') { stack.push(stack.pop() * num); } else if (sign == '/') { stack.push(stack.pop() / num); } sign = s.charAt(i); num = 0; } } int res = 0; for (int i : stack) { res += i; } return res; } }
|