Basic Calculator II

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.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Tags

• String
• Stack
• Math

Thought

Since there is no bracket here, we don't need to implement it with RPN like previous problem (but that algorithm still works!). We use the stack to solve the problem based on four different operations.

Code

class Solution(object):
    def helper(self, stack, sign, number):
        if sign == '+':
            stack.append(number)
        elif sign == '-':
            stack.append(-number)
        elif sign == '*':
            stack.append(stack.pop() * number)
        else:
            # The integer division should truncate toward zero.
            tmp = stack.pop()
            if tmp // number < 0 and tmp % number != 0:
                stack.append(tmp // number + 1)
            else:
                stack.append(tmp // number)
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0
        stack = []
        sign = '+'
        while i <= len(s):
            if i == len(s):
                self.helper(stack, sign, number)
                break
            c = s[i]
            if c.isdigit():
                start = i
                while i < len(s) and s[i].isdigit():
                    i += 1
                number = int(s[start:i])
                continue
            if c in '+-*/':
                self.helper(stack, sign, number)
                sign = c
            i += 1
        return sum(stack)