224. Basic Calculator

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 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.

Problem URL

---

Solution

给一个String代表的只有+ - （）的表达式，保证合法，计算它的结果。

Using a stack to maintain the result before a () bracket. We use initial sign = 1. every time we meet a non-digit char, it is the time to calculate previous number value to result. It is calculating previour number and assigning number and sing value for next number. After the iteration, if we still have unadded number, remember add it.

Code

class Solution { public int calculate(String s) { Stack<Integer> stack = new Stack<>(); int number = 0, result = 0, sign = 1; for (int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if (Character.isDigit(ch)){ number = number * 10 + ch - '0'; } if (ch == '+'){ result += sign * number; number = 0; sign = 1; } if (ch == '-'){ result += sign * number; number = 0; sign = -1; } if (ch == '('){ stack.push(result); stack.push(sign); result = 0; sign = 1; } if (ch == ')'){ result += sign * number; number = 0; result *= stack.pop();//pop out sign first result += stack.pop();//pop out original result; } } if (number != 0){ result += sign * number; } return result; } }

Time Complexity: O(n) Space Complexity: O(n)

---

Review