224. Basic Calculator

• Difficulty: Hard

• Topics: Math, Stack

• Similar Questions:

  • Evaluate Reverse Polish Notation

  • Basic Calculator II

  • Different Ways to Add Parentheses

  • Expression Add Operators

  • Basic Calculator III

Problem:

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

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Solutions:

class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int sign = 1;
        int val = 0;
        stk.push(0);
        for (int i = 0; i < s.length(); ++i) {
            switch(s[i]) {
                case '+': {
                    stk.top() = stk.top() + sign * val;
                    sign = 1; // reset
                    val = 0;
                    break;
                }
                case '-': {
                    stk.top() = stk.top() + sign * val;
                    sign = -1; // reset
                    val = 0;
                    break;
                }
                case ' ': {
                    break;
                }
                case '(': {
                    stk.push(sign);
                    sign = 1; // reset
                    val = 0;
                    stk.push(0);
                    break;
                }
                case ')': {
                    stk.top() = stk.top() + sign * val;
                    int expVal = stk.top();
                    stk.pop();
                    expVal = expVal * stk.top();
                    stk.pop();
                    stk.top() += expVal;
                    val = 0; // reset
                    sign = 1;
                    break;
                }
                default: {
                    val = val * 10 - '0' + s[i] ;
                    break;
                }
            }

        }

        return stk.top() + val * sign; // including all
    }
};