逆波兰表达式求值

yingl · yingl · commit a9009c2bb841 · 2016-08-01T14:39:54.000+08:00
diff --git a/evaluate_reverse_polish_notation.py b/evaluate_reverse_polish_notation.py
@@ -0,0 +1,31 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param {string[]} tokens The Reverse Polish Notation
+    # @return {int} the value
+    def evalRPN(self, tokens):
+        # Write your code here
+        ret = []
+        for item in tokens:
+            if self.isOperator(item):
+                right_val = ret.pop()
+                left_val = ret.pop()
+                if item == '*':
+                    ret.append(left_val * right_val)
+                elif item == '/':
+                    # Python&#23545;&#20110;&#27491;&#36127;&#25968;&#30456;&#38500;&#26377;&#38382;&#39064;&#65292;&#38656;&#35201;&#21333;&#29420;&#22788;&#29702;
+                    hack = ((left_val > 0) and (right_val < 0)) or ((left_val < 0) and (right_val > 0))
+                    div = abs(left_val) / abs(right_val)
+                    if hack:
+                        div = -1 * int(div)
+                    ret.append(div)
+                elif item == '+':
+                    ret.append(left_val + right_val)
+                else:
+                    ret.append(left_val - right_val)
+            else:
+                ret.append(int(item))
+        return 0 if not ret else ret[0]
+
+    def isOperator(self, item):
+        return (item == '+') or (item == '-') or (item == '*') or (item == '/')
