Leetcode: Basic Calculator II

Basic Calculator II



Similar Problems:


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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/basic-calculator-ii
## Basic Ideas: +- yield to */
##
##           When we found one operator as +/, look for the next operator
##           When we found one operator as */, we solve it immediately
## Complexity: Time O(n), Space O(n)
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = s.replace(' ', '')
        i = 0
        length = len(s)
        # solve */
        stack = []
        while i<length:
            if s[i].isdigit():
                # get the num
                num_str = ''
                while i<length and s[i].isdigit():
                    num_str = "%s%s" % (num_str, s[i])
                    i += 1
                stack.append(num_str)
            elif s[i] in '*/':
                num1 = int(stack.pop())
                num_str = ''
                op = s[i]
                # find the next number
                i += 1
                while i<length and s[i].isdigit():
                    num_str = "%s%s" % (num_str, s[i])
                    i += 1
                num2 = int(num_str)
                if op == '*':
                    num1 = num1*num2
                else:
                    num1 = num1/num2
                stack.append(str(num1))
            else:
                # +-
                stack.append(s[i])
                i += 1

        # solve +-
        res, i = 0, 0
        while i<len(stack):
            element = stack[i]
            if element in '+-':
                num2 = stack[i+1]
                i = i+2
                if element == '+':
                    res += int(num2)
                else:
                    res -= int(num2)
            else:
                res += int(element)
                i += 1
        return res

# s = Solution()
# print s.calculate(" 3+5 / 2 ") # 5
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.