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.

Approach 3: general solution is to build postfix notation and evaluate.

Code (Python)

Approach 1:

import re

class Solution:
    def calculate(self, expr: str) -> int:
        # trick: wrap the original expression with a bracket to cut corner cases
        tokens = ['('] + self._tokenize(expr) + [')']
        if not tokens:
            return 0

        stack = []
        for token in tokens:
            if token != ')':
                stack.append(token)
            else:
                temp_result = 0
                while len(stack) and stack[-1] != '(':
                    num = int(stack.pop())
                    op = stack.pop()
                    if op == '(':
                        temp_result += num
                        stack.append(temp_result)
                        break
                    else:
                        temp_result += num if op == '+' else -num
                # this handles cases like 1-(-2)
                if stack[-1] == '(':
                    stack.pop()
                    stack.append(temp_result)
        return stack[0]

    def _tokenize(self, expression):
        return [e for e in re.split('(\D)', expression) if e and not re.match('\s', e)]

Approach 3:

class Solution:
    def calculate(self, s: str) -> int:
        # http://bookshadow.com/weblog/2015/06/09/leetcode-basic-calculator/
        # idea for all calculators: convert to postfix notation, then evalutate
        # example of postfix: (a+b)*c - (a+b)/d => [a, b, +, c, *, a, b, + d, /, -]
        # this following solution work for all operators in +-*/
        return self._evaluate(self._to_postfix(s))
    
    def _to_postfix(self, expression):
        # two stacks: a stack (list) storing postfix, and an operator stack to store operators and left paren 
        # operators have priorities: +- has priority 1, */ has priority 2
        postfix = []
        operators = []
        value = '' # to handle multiple digits
        ops = {
            '+': 1,
            '-': 1,
            '*': 2,
            '/': 2
        }
        
        for char in expression:
            if not char or char == ' ':
                continue
            if char.isdigit():
                value += char
            else:
                if value:
                    postfix.append(int(value))
                    value = ''
                if char == '(':
                    operators.append(char)
                elif char in ops:
                    # pop from operators with higher or equal priority, or until meet a (, then push char onto operators
                    while operators and operators[-1] != '(' and ops[operators[-1]] >= ops[char]:
                        postfix.append(operators.pop())
                    operators.append(char)
                else: # )
                    # pop from operators until meet a (
                    while operators and operators[-1] != '(':
                        postfix.append(operators.pop())
                    operators.pop()
        # pop remaining digits first
        if value:
            postfix.append(int(value))
        # pop remaining operators
        while operators:
            postfix.append(operators.pop())
    
        return postfix
    
    def _evaluate(self, postfix):
        ops = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: a / b
        }
        current = []
        for item in postfix:
            if item in ops:
                val2, val1 = current.pop(), current.pop()
                current.append(ops[item](val1, val2))
            else:
                current.append(item)
        return current[0]

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;
    }
};