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

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.

# Solution

Approach 1: Stack for everything.

Approach 2: Stack for signs.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Stack for everything.
class Solution {
public:
    int calculate(string s) {
        stack<string> st;
        st.push("(");
        int head = 0;
        for (int i = 0; i <= s.size(); ++i)
        {
            if (i == s.size() || !isdigit(s[i]))
            {
                if (i > head)
                {
                    st.push(s.substr(head, i - head));
                }
                if (i == s.size() || s[i] == ')')
                {
                    int total = stoi(st.top());
                    st.pop();
                    if (st.top() == "-")
                        total = 0 - total;
                    while (!st.empty() && st.top() != "(")
                    {
                        st.pop(); // pop "+" or "-".
                        int num = stoi(st.top());
                        st.pop();
                        if (st.top() == "-")
                            num = 0 - num;
                        total += num;
                    }
                    st.pop(); // pop "(".
                    st.push(std::to_string(total));
                }
                else if (i < s.size() && s[i] != ' ')
                {
                    st.push(string(1, s[i]));
                }
                head = i + 1;
            }
        }
        return stoi(st.top());
    }
};

Approach 2:

// Stack for signs.
class Solution {
public:
    int calculate(string s) {
        stack<int> stSign;
        stSign.push(1);
        int res = 0;
        int sign = 1;
        int head = 0;
        for (int i = 0; i <= s.size(); ++i)
        {
            if (i == s.size() || !isdigit(s[i]))
            {
                if (i > head)
                {
                    res += sign * stoi(s.substr(head, i - head));
                }
                if (i < s.size())
                {
                    if (s[i] == '+')
                        sign = stSign.top();
                    else if (s[i] == '-')
                        sign = 0 - stSign.top();
                    else if (s[i] == '(')
                        stSign.push(sign);
                    else if (s[i] == ')')
                        stSign.pop();
                }
                head = i + 1;
            }
        }
        return res;
    }
};