A different fast Python solution, easy to understand


  • 0
    C

    The idea is very simple :

    1. split the string by +-
    2. calculate substring (they are either digits or string that only contains */ operators)
    3. sum all the elements

    Suppose we have an input s = "3+2-4/5*6/2+3*4-2",

    we use a list pn to keep track of the relative order of +- operators, replace - with +, and then split it by using s.replace("-", "+").split("+")

      ['3', '2', '4/5*6/2', '3*4',  '2']
    
         [1,   -1,        1,     -1]    <= pn
    

    As we can see, the final result is the sum of the values of substrings. ( pn would tell us whether we should add or subtract the next element).


    The next step is to calculate the values of substrings (without +-). For substrings with */, we can use a similar trick to split it and then calculate the result by calling self.cal(substring). Once it's done, we get the following and it will be easy to calculate the final result:

      [3,   2,   0,  12,   2]
    
         [1,  -1,  1,   -1]    <= pn
    

    Putting it together, we get this function.

    The runtime is ~220 ms, fast enough (beating ~ 83%).

    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = s.replace(" ", "")
        pn = [1 if c=="+" else -1 for c in s if c in "+-"] # order of +- signs
        sList = [self.cal(c) for c in s.replace("-", "+").split("+")]
    
        return sList[0] + sum([sList[i+1]*pn[i] for i in xrange(len(pn))])
    
        
    def cal(self, s): # calculate the values of substrings "WITHOUT +-"
        if "*" not in s and "/" not in s:
            return int(s)
    
        md = [1 if c=="*" else -1 for c in s if c in "*/"] # order of */ signs
        sList = [int(i) for i in s.replace("/", "*").split("*")]
        
        res, i = sList[0], 0
        while res != 0 and i < len(md):
            if md[i] == 1:
                res *= sList[i+1]
            else:
                res //= sList[i+1]
            i += 1
        return res

Log in to reply
 

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