Implement post fix evaluation

cheec · cheec · commit 15d6cbc2fa03 · 2019-10-06T17:03:40.000+08:00
diff --git a/DataStructures/Stacks/Algorithms_toDo.txt b/DataStructures/Stacks/Algorithms_toDo.txt
@@ -1,4 +1,3 @@
 + stack
 + next greater element
-+ postfix evaluation
-+ balanced parentheses
++ balanced parentheses
diff --git a/DataStructures/Stacks/postFixEvaluation.js b/DataStructures/Stacks/postFixEvaluation.js
@@ -0,0 +1,35 @@
+function postFixEvaluation(expression) {
+    if (typeof expression !== 'string' || expression.length === 0) {
+        throw 'Invalid post fix expression.';
+    }
+
+    var stack = [];
+    for (var i = 0; i < expression.length; i++) {
+        var curr = expression[i];
+        if (curr.match(/^\d$/)) {
+            stack.push(curr - '0');
+        } else if (curr.match(/^[+-/*]$/)) {
+            if (stack.length < 2) {
+                throw 'Invalid post fix expression.';
+            }
+
+            var op = {
+                '+' : function(a, b) { return a + b },
+                '-': function(a, b) { return b - a },
+                '/': function(a, b) { return b / a },
+                '*': function(a, b) { return a * b }
+            };
+            var first = stack.pop();
+            var second = stack.pop();
+
+            stack.push(op[curr](first, second));
+        } else {
+            throw 'Invalid post fix expression.';
+        }
+    }
+
+    return stack.pop();
+}
+
+console.log(postFixEvaluation("235*+8-")); // === 9
+console.log(postFixEvaluation("23/")); // === 0.66
