180ms Python solution with detailed comments, O(n) time, O(1) space

  • 1
    class Solution(object):
        def calculate(self, s):
            higher = set(['*','/'])
            lower = set(['+','-'])
            operators = higher.union(lower)
            # quick reference for the operators
            s = s.strip(' ')+'+'
            # adding a ending + sign is useful to handle the last number
            # since main loop below only updates totalResult upon an operator
            totalResult = 0
            higherValue = None 
            # int higherValue imitates a stack, in a sense that it updates value upon every push
            higherValueOperator = '+'
            prevOperator = '+'
            temp = ''
            # initialize variables 
            for i in s:
                if i in operators:
                    num = int(temp)
                    temp = ''
                    # whenever encounter an operator, parse the number
                    if i in lower:
                        if higherValue == None:
                            totalResult += num if prevOperator == '+' else -num
                            # simple case: just update totalResult
                            # interesting case: when a number is preceeded by higher operator
                            # but followed by a lower operator, we wrap up higherValue
                            # and put higherValue into totalResult
                            higherValue = higherValue*num if prevOperator=='*' else higherValue/num
                            totalResult += higherValue if higherValueOperator == '+' else -higherValue
                            higherValue = None
                    else: # where i is a higher operator
                        if higherValue != None:
                            higherValue = higherValue*num if prevOperator=='*' else higherValue/num
                            higherValue = num
                            higherValueOperator = prevOperator 
                    prevOperator = i
                else: # where i is a digit
                    temp += i
            return totalResult

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.