My Python solution use two stack


  • 0
    H

    To deal with the parentheses situation, I use one stack to store the operator and the other to store the calculated value in the parentheses. Then just pop up all the element in the operator stack.

    def calculate(self, s):
        numstack = []
        opstack = []
        i = len(s) -1
        while i > -1:
            if s[i] in '0123456789':
                j  = i
                while  i > -1 and s[i] in '0123456789':
                    i -= 1
                i += 1
                numstack.append(int(s[i:j+1]))
            else:
                if s[i] in ')+-':
                    opstack.append(s[i])
                if s[i] == '(':
                    while opstack[-1] != ')':
                        if opstack.pop() == '+':
                            numstack.append(numstack.pop()+numstack.pop())
                        else:
                            numstack.append(numstack.pop()-numstack.pop())
                    opstack.pop()
            i -= 1
        while opstack:
            if opstack.pop()=='+':
                numstack.append(numstack.pop()+numstack.pop())
            else:
                numstack.append(numstack.pop()-numstack.pop())
        return numstack[-1]

Log in to reply
 

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