[LeetCode] Basic Calculator

Basic Calculator

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.

Solution: Stack.

If we encounter +, - or (, we push them in the stack.

If we encounter ), we know the expression inside () has been evaluated. Pop the result for that expression, and pop (. And perform one operation if necessary.

if we encounter a number, perform one operation if necessary.

Remarks. One may solve this recursively by working from the end of the string.

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

public class Solution { private boolean isDigit(char ch) { return ch >= '0' && ch <= '9'; } private void pushOrAddOrMinus( String str, Stack<String> stack ) { if (stack.empty() || stack.peek().equals("(")) { stack.push(str); return; } int val = Integer.valueOf(str); if (stack.peek().equals("+")) { stack.pop(); int val_o = Integer.valueOf(stack.pop()); stack.push(String.valueOf(val_o + val)); } else if (stack.peek().equals("-")) { stack.pop(); int val_o = Integer.valueOf(stack.pop()); stack.push(String.valueOf(val_o - val)); } } public int calculate(String s) { if (s.length() == 0) { return 0; } Stack<String> stack = new Stack<String>(); int i = 0; while (i < s.length()) { if (s.charAt(i) == '+') { stack.push("+"); i++; } else if (s.charAt(i) == '-') { stack.push("-"); i++; } else if (s.charAt(i) == '(') { stack.push("("); i++; } else if (s.charAt(i) == ')') { String str = stack.pop(); stack.pop(); i++; pushOrAddOrMinus(str, stack); } else if (s.charAt(i) == ' ') { i++; } else { int j = i + 1; while (j < s.length() && isDigit(s.charAt(j))) { j++; } String str = s.substring(i, j); i = j; pushOrAddOrMinus(str, stack); } } return Integer.valueOf(stack.pop()); } }