227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

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

Solution

Approach 1: Stack.

Approach 2: Non-stack.

Code (Python)

Approach 2:

class Solution(object):
    def calculate(self, string):
        """
        :type s: str
        :rtype: int
        """
        string = [x for x in re.split('(\D)',string.strip()) if x and not re.match('\s', x)]
        # i goes in steps of 2
        result = int(string[0])
        prev_val = result
        i = 1
        while i < len(string):
            if string[i] == '+' or string[i] == '-':
                prev_val = int(string[i+1]) if string[i] == '+' else -int(string[i+1])
                result += prev_val
            # if * or /, cancel prev result, add up and add prev result
            elif string[i] == '*' or string[i] == '/':
                result -= prev_val
                if string[i] == '*':
                    prev_val *= int(string[i+1])
                else:
                    # corrections for python division
                    correction = 0
                    if prev_val < 0 and prev_val % int(string[i+1]) != 0:
                        correction = 1
                    prev_val = int(prev_val // int(string[i+1])) + correction
                result += prev_val  
            i += 2
        return result

Code (C++)

Approach 1:

// Stack.
class Solution {
private:
    stack<int> st;
    void tryCalculate() {
        if (st.size() > 2)
        {
            int b = st.top();
            st.pop();
            char op = st.top();
            st.pop();
            int a = st.top();
            st.pop();
            switch (op)
            {
                case '+' : st.push(a + b); break;
                case '-' : st.push(a - b); break;
                case '*' : st.push(a * b); break;
                case '/' : st.push(a / b); break;
            }
        }
    }
public:
    int calculate(string s) {
        int head = 0;
        int tail = 0;
        bool nextCal = false;
        while (tail <= s.size())
        {
            // Handle the number.
            if ((tail > head) && (tail == s.size() || !isdigit(s[tail])))
            {
                int num = stoi(s.substr(head, tail - head));
                st.push(num);
                if (nextCal || tail == s.size())
                    tryCalculate();
                nextCal = false;
            }
            // Handle the non-number.
            if (tail < s.size() && !isdigit(s[tail]))
            {
                if (s[tail] == '*' || s[tail] == '/')
                {
                    st.push(s[tail]);
                    nextCal = true;
                }
                else if (s[tail] == '+' || s[tail] == '-')
                {
                    tryCalculate();
                    st.push(s[tail]);
                }
                head = tail + 1;
            }
            tail++;    
        }
        tryCalculate();
        return st.top();
    }
};

Approach 2:

// Non-stack.
// e.g., treat "3-2*2+1" as "0+3-2*2+1"
// init: prev = 0;
// for 0+3 : res += prev (0);  prev = 0; prev = prev + 3 (0 + 3)
// for 3-2 : res += prev (3);  prev = 0; prev = prev - 2 (0 - 2)
// for 2*2 : noop                      ; prev = prev * 2 (-2 * 2)
// for 2+1 : res += prev (-4); prev = 0; prev = prev + 1 (0 + 1)
// end: res += prev (1)
class Solution {
public:
    int calculate(string s) {
        int head = 0;
        int tail = 0;
        int prev = 0;
        char op = '+';
        int res = 0;
        while (tail <= s.size())
        {
            // Handle the number.
            if ((tail > head) && (tail == s.size() || !isdigit(s[tail])))
            {
                int curr = stoi(s.substr(head, tail - head));
                if (op == '+' || op == '-')
                {
                    res += prev;
                    prev = 0;
                }
                switch (op)
                {
                    case '+' : prev = prev + curr; break;
                    case '-' : prev = prev - curr; break;
                    case '*' : prev = prev * curr; break;
                    case '/' : prev = prev / curr; break;
                }
            }
            // Handle the non-number.
            if (tail < s.size() && !isdigit(s[tail]))
            {
                if (s[tail] != ' ')
                    op = s[tail];
                head = tail + 1;
            }
            tail++;    
        }
        return res + prev;
    }
};