Question: https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/
Question Name: Evaluate Reverse Polish Notation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | class Solution: # @param tokens, a list of string # @return an integer def evalRPN(self, tokens, method = "Ite"): if method == "Ite": return self.evalRPNIte(tokens) elif method == "Rec": return self.evalRPNRec(tokens) else: raise Exception("Invalid method.") # @param tokens, a list of string # @return an integer def evalRPNIte(self, tokens): ''' Eval the RPN in an iterative method. ''' waiting = [] while len(tokens) != 0: token = tokens.pop() if not token in set(["+", "-", "*", "/"]): # This is an operand. token = int(token) while len(waiting) != 0 and type(waiting[-1]) == int: otherOperand = waiting.pop() operator = waiting.pop() if operator == "+": token += otherOperand elif operator == "-": token -= otherOperand elif operator == "*": token *= otherOperand elif operator == "/": # http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result # Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0. if (token > 0 and otherOperand > 0) or (token < 0 and otherOperand < 0): token = abs(token) // abs(otherOperand) else: token = - (abs(token) // abs(otherOperand)) else: raise Exception("Unknown Token.") waiting.append(token) else: # This is an operator. waiting.append(token) return waiting[-1] # @param tokens, a list of string # @return an integer def evalRPNRec(self, tokens): ''' Eval the RPN in a recursive method. ''' assert len(tokens) != 0 token = tokens.pop() if not token in set(["+", "-", "*", "/"]): # This is an operand. return int(token) else: # This is an operator. # The corresponding operands are in the stack. So the second # operand is on the top of the first one. secondParameter = self.evalRPN(tokens) firstParameter = self.evalRPN(tokens) if token == "+": return firstParameter + secondParameter elif token == "-": return firstParameter - secondParameter elif token == "*": return firstParameter * secondParameter elif token == "/": # http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result # Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0. if secondParameter == 0: raise ZeroDivisionError() elif firstParameter > 0 and secondParameter > 0: return firstParameter // secondParameter elif firstParameter < 0 and secondParameter > 0: return - ((-firstParameter) // secondParameter) elif firstParameter > 0 and secondParameter < 0: return - (firstParameter // (-secondParameter)) else: return (-firstParameter) // (-secondParameter) else: raise Exception("Unknown Token.") |