Share my Python solution using Reverse Polish Notation


  • 0
    D

    The idea is to convert input string into RPN. Then get the value using the result from "Evaluate Reverse Polish Notation". The speed is not fast (around 400 ms)

    class Solution:
        # @param {string} s
        # @return {integer}
        def calculate(self, s):
            def _evalRPN(tokens):
                operands = []
                for token in tokens:
                    if token in '+-':
                        # meet an operator, pop operand one and two
                        op2, op1 = operands.pop(), operands.pop()
                        if token == '+':
                            operands.append(op1 + op2)
                        else:
                            operands.append(op1 - op2)
                    else:
                        # push operand onto stack
                        operands.append(int(token))
                return operands[0]
    
            # remove spaces
            s = s.replace(' ', '')
            index, length = 0, len(s)
            operators, tokens = [], []
            while index < length:
                if s[index].isdigit():
                    # number
                    start = index
                    while index < length and s[index].isdigit():
                        index += 1
                    tokens.append(s[start : index])
                else:
                    if s[index] in '+-':
                        # push top operator onto tokens if it is not open parentheses
                        if operators and operators[-1] != '(':
                            tokens.append(operators.pop())
                        operators.append(s[index])
                    elif s[index] == '(':
                        # push open parentheses onto stack
                        operators.append(s[index])
                    else:
                        # close parentheses
                        while operators[-1] != '(':
                            # push previous operators onto tokens till we meet open parentheses
                            tokens.append(operators.pop())
                        # remove open parentheses from stack
                        operators.pop()
                    index += 1
    
            # push remaining operators onto tokens
            while operators:
                tokens.append(operators.pop())
            # evaluate as reverse polish notation
            return _evalRPN(tokens)

Log in to reply
 

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