Question

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

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0

        stack = list()
        curr_num = 0
        should_eval = False

        s = s.replace(' ', '') # remove spaces
        for c in s:
            if c.isdigit():
                curr_num = curr_num * 10 + int(c)
            else:
                stack.append(curr_num)
                curr_num = 0
                if should_eval:
                    v1 = stack.pop()
                    op = stack.pop()
                    v2 = stack.pop()
                    if op == '*':
                        stack.append(v1 * v2)
                    else:
                        stack.append(v2 // v1)

                stack.append(c)
                if c == '+' or c == '-':
                    should_eval = False
                else:
                    should_eval = True

        stack.append(curr_num)
        if should_eval:
            v1 = stack.pop()
            op = stack.pop()
            v2 = stack.pop()
            if op == '*':
                stack.append(v1 * v2)
            else:
                stack.append(v2 // v1)

        res = 0
        while len(stack) > 1:
            v = stack.pop()
            op = stack.pop()
            if op == '+':
                res += v
            else:
                res -= v

        res += stack.pop()
        return res