Saturday, August 29, 2015

Leetcode 224. Basic Calculator

https://leetcode.com/problems/basic-calculator/

For problems concerning sequence, stack is a good choice. Here we can build two stacks, one for operators, one for operands. Note the numbers might be greater than 9, so converting string to integer needs more attention.

Another problem is the process direction. For instance, 2-1+2=3, but if we use stack from left to right, N=[2,1,2], S=[-,+], we cannot use pop because in that way it would be 2-2+1=-1, so we have to reverse both N and S. Therefore we could reverse s and use pop operation.

Solution:
# T:O(n) S:O(n)
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        operands, operators = [], []
        operand = ""
        for i in reversed(xrange(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0  or not s[i-1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == ')' or s[i] == '+' or s[i] == '-':
                operators.append(s[i])
            elif s[i] == '(':
                while operators[-1] != ')':
                    self.compute(operands, operators)
                operators.pop()
                
        while operators:
            self.compute(operands, operators)
            
        return operands[-1]

    def compute(self, operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)
Run Time: 392 ms

No comments:

Post a Comment