DmitrySoshnikov · July 11, 2025 11:30 · Sep 5, 2020 · Sep 5, 2020 · Sep 5, 2020 · Sep 24, 2011
diff --git a/shunting-yard-algorithm.js b/shunting-yard-algorithm.js
@@ -58,7 +58,7 @@ function shuntingYard(string) {
   let output = [];
   let stack = [];
 
-  for (let k = 0, length = string.length; k < length;  k++) {
+  for (let k = 0; k <string.length;  k++) {
 
     // current char
     const ch = string[k];
@@ -140,18 +140,21 @@ function shuntingYard(string) {
 
     }
 
-    else throw "Unknown token " + ch;
+    else {
+      throw new Error(`Unknown token: ${ch}`);
+    }
 
   }
 
   // when there are no more tokens to read:
   // while there are still operator tokens in the stack:
-  while (stack.length) {
+  while (stack.length > 0) {
 
-    let c = stack.pop();
+    const c = stack.pop();
 
-    if (c == "(" || c == ")")
-      throw "Error: parentheses mismatched";
+    if (c === "(" || c === ")") {
+      throw new Error("Parentheses mismatched");
+    }
 
     // push it to the output
     output.push(c);
@@ -167,4 +170,4 @@ function shuntingYard(string) {
 console.log("2 + 2 + 2 ->", shuntingYard("2 + 2 + 2")); // 2 2 + 2 +
 console.log("2 + 2 * 2 ->", shuntingYard("2 + 2 * 2")); // 2 2 2 * +
 console.log("(2 + 2) * 2 ->", shuntingYard("(2 + 2) * 2")); // 2 2 + 2 *
-console.log("2 / (4 * 2) ->", shuntingYard("2 / (4 * 2)")); // 2 4 2 * /
+console.log("2 / (4 * 2) ->", shuntingYard("2 / (4 * 2)")); // 2 4 2 * /
diff --git a/shunting-yard-algorithm.js b/shunting-yard-algorithm.js
@@ -167,4 +167,4 @@ function shuntingYard(string) {
 console.log("2 + 2 + 2 ->", shuntingYard("2 + 2 + 2")); // 2 2 + 2 +
 console.log("2 + 2 * 2 ->", shuntingYard("2 + 2 * 2")); // 2 2 2 * +
 console.log("(2 + 2) * 2 ->", shuntingYard("(2 + 2) * 2")); // 2 2 + 2 *
-console.log("2 / (4 * 2) ->", shuntingYard("2 / (4 * 2)")); // 2 2 + 2 *
+console.log("2 / (4 * 2) ->", shuntingYard("2 / (4 * 2)")); // 2 4 2 * /
diff --git a/shunting-yard-algorithm.js b/shunting-yard-algorithm.js
@@ -6,6 +6,8 @@
  *
  * by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
  * MIT Style License
+ *
+ * (C) 2011, updated on 2020
  */
 
 // helper, top element of an array w/o removing it
@@ -14,11 +16,11 @@ Array.prototype.peek = function () {
 };
 
 // operators set
-var operators = {"+": 1, "-": 1, "*": 1, "/": 1};
+const operators = {"+": 1, "-": 1, "*": 1, "/": 1};
 
 // associations (left / right) sets
-var leftAssoc =  {"*": 1, "/": 1, "%": 1, "+": 1, "-": 1};
-var rightAssoc = {"=": 1, "!": 1};
+const leftAssoc =  {"*": 1, "/": 1, "%": 1, "+": 1, "-": 1};
+const rightAssoc = {"=": 1, "!": 1};
 
 /**
  * precedenceOf
@@ -30,7 +32,7 @@ var rightAssoc = {"=": 1, "!": 1};
  * 4            =               right to left
  */
 
-var precedenceOf = {
+const precedenceOf = {
   "!": 4,
 
   "*": 3,
@@ -53,21 +55,23 @@ var precedenceOf = {
  */
 function shuntingYard(string) {
 
-  var output = [];
-  var stack = [];
+  let output = [];
+  let stack = [];
 
-  for (var k = 0, length = string.length; k < length;  k++) {
+  for (let k = 0, length = string.length; k < length;  k++) {
 
     // current char
-    var ch = string[k];
+    const ch = string[k];
 
     // skip whitespaces
-    if (ch == " ")
+    if (ch === " ") {
       continue;
+    }
 
     // if it's a number, add it to the output queue
-    if (/\d/.test(ch))
+    if (/\d/.test(ch)) {
       output.push(ch);
+    }
 
     // TODO: if the token is a function token, then push it onto the stack
 
@@ -76,13 +80,13 @@ function shuntingYard(string) {
     // if the token is an operator, op1, then:
     else if (ch in operators) {
 
-      var op1 = ch; // just for readability
+      const op1 = ch; // just for readability
 
       // while ...
-      while (stack.length) {
+      while (stack.length > 0) {
 
         // ... there is an operator token, op2, at the top of the stack
-        var op2 = stack.peek();
+        const op2 = stack.peek();
 
         if (op2 in operators && (
             // and op1 is left-associative and its precedence is less than or equal to that of op2,
@@ -91,7 +95,7 @@ function shuntingYard(string) {
             (op1 in rightAssoc && (precedenceOf[op1] < precedenceOf[op2]))
         )) {
 
-          // push op2 onto the output queue (it's already popped from the stack);
+          // push op2 onto the output queue
           output.push(stack.pop()); // op2
 
         } else {
@@ -106,19 +110,20 @@ function shuntingYard(string) {
     }
 
     // if the token is a left parenthesis, then push it onto the stack.
-    else if (ch == "(")
+    else if (ch === "(") {
       stack.push(ch);
+    }
 
     // if the token is a right parenthesis:
-    else if (ch == ")") {
+    else if (ch === ")") {
 
-      var foundLeftParen = false;
+      let foundLeftParen = false;
 
       // until the token at the top of the stack is a left parenthesis,
       // pop operators off the stack onto the output queue
-      while (stack.length) {
-        var c = stack.pop();
-        if (c == "(") {
+      while (stack.length > 0) {
+        const c = stack.pop();
+        if (c === "(") {
           foundLeftParen = true;
           break;
         } else {
@@ -127,11 +132,9 @@ function shuntingYard(string) {
       }
 
       // if the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
-      if (!foundLeftParen)
-        throw "Error: parentheses mismatched";
-
-      // pop the left parenthesis from the stack, but not onto the output queue.
-      stack.pop();
+      if (!foundLeftParen) {
+        throw new Error("Parentheses mismatched");
+      }
 
       // TODO: if the token at the top of the stack is a function token, pop it onto the output queue.
 
@@ -145,7 +148,7 @@ function shuntingYard(string) {
   // while there are still operator tokens in the stack:
   while (stack.length) {
 
-    var c = stack.pop();
+    let c = stack.pop();
 
     if (c == "(" || c == ")")
       throw "Error: parentheses mismatched";
@@ -164,3 +167,4 @@ function shuntingYard(string) {
 console.log("2 + 2 + 2 ->", shuntingYard("2 + 2 + 2")); // 2 2 + 2 +
 console.log("2 + 2 * 2 ->", shuntingYard("2 + 2 * 2")); // 2 2 2 * +
 console.log("(2 + 2) * 2 ->", shuntingYard("(2 + 2) * 2")); // 2 2 + 2 *
+console.log("2 / (4 * 2) ->", shuntingYard("2 / (4 * 2)")); // 2 2 + 2 *
diff --git a/shunting-yard-algorithm.js b/shunting-yard-algorithm.js
@@ -0,0 +1,166 @@
+/**
+ * Shunting yard algorithm
+ * See: http://en.wikipedia.org/wiki/Shunting_yard_algorithm
+ *
+ * Converts infix notation to postfix notation
+ *
+ * by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ * MIT Style License
+ */
+
+// helper, top element of an array w/o removing it
+Array.prototype.peek = function () {
+  return this[this.length - 1];
+};
+
+// operators set
+var operators = {"+": 1, "-": 1, "*": 1, "/": 1};
+
+// associations (left / right) sets
+var leftAssoc =  {"*": 1, "/": 1, "%": 1, "+": 1, "-": 1};
+var rightAssoc = {"=": 1, "!": 1};
+
+/**
+ * precedenceOf
+ *
+ * precedence   operators       associativity
+ * 1            !               right to left
+ * 2            * / %           left to right
+ * 3            + -             left to right
+ * 4            =               right to left
+ */
+
+var precedenceOf = {
+  "!": 4,
+
+  "*": 3,
+  "/": 3,
+  "%": 3,
+
+  "+": 2,
+  "-": 2,
+
+  "=": 1
+};
+
+/**
+ * Shunting_yard_algorithm
+ * @param {String} string
+ *
+ * TODO:
+ *    - support digits > 10
+ *    - functions
+ */
+function shuntingYard(string) {
+
+  var output = [];
+  var stack = [];
+
+  for (var k = 0, length = string.length; k < length;  k++) {
+
+    // current char
+    var ch = string[k];
+
+    // skip whitespaces
+    if (ch == " ")
+      continue;
+
+    // if it's a number, add it to the output queue
+    if (/\d/.test(ch))
+      output.push(ch);
+
+    // TODO: if the token is a function token, then push it onto the stack
+
+    // TODO: if the token is a function argument separator (e.g., a comma):
+
+    // if the token is an operator, op1, then:
+    else if (ch in operators) {
+
+      var op1 = ch; // just for readability
+
+      // while ...
+      while (stack.length) {
+
+        // ... there is an operator token, op2, at the top of the stack
+        var op2 = stack.peek();
+
+        if (op2 in operators && (
+            // and op1 is left-associative and its precedence is less than or equal to that of op2,
+            (op1 in leftAssoc && (precedenceOf[op1] <= precedenceOf[op2])) ||
+            // or op1 is right-associative and its precedence is less than that of op2,
+            (op1 in rightAssoc && (precedenceOf[op1] < precedenceOf[op2]))
+        )) {
+
+          // push op2 onto the output queue (it's already popped from the stack);
+          output.push(stack.pop()); // op2
+
+        } else {
+          break;
+        }
+
+      }
+
+      // push op1 onto the stack
+      stack.push(op1);
+
+    }
+
+    // if the token is a left parenthesis, then push it onto the stack.
+    else if (ch == "(")
+      stack.push(ch);
+
+    // if the token is a right parenthesis:
+    else if (ch == ")") {
+
+      var foundLeftParen = false;
+
+      // until the token at the top of the stack is a left parenthesis,
+      // pop operators off the stack onto the output queue
+      while (stack.length) {
+        var c = stack.pop();
+        if (c == "(") {
+          foundLeftParen = true;
+          break;
+        } else {
+          output.push(c);
+        }
+      }
+
+      // if the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
+      if (!foundLeftParen)
+        throw "Error: parentheses mismatched";
+
+      // pop the left parenthesis from the stack, but not onto the output queue.
+      stack.pop();
+
+      // TODO: if the token at the top of the stack is a function token, pop it onto the output queue.
+
+    }
+
+    else throw "Unknown token " + ch;
+
+  }
+
+  // when there are no more tokens to read:
+  // while there are still operator tokens in the stack:
+  while (stack.length) {
+
+    var c = stack.pop();
+
+    if (c == "(" || c == ")")
+      throw "Error: parentheses mismatched";
+
+    // push it to the output
+    output.push(c);
+
+  }
+
+  return output.join(" ");
+
+}
+
+// tests
+
+console.log("2 + 2 + 2 ->", shuntingYard("2 + 2 + 2")); // 2 2 + 2 +
+console.log("2 + 2 * 2 ->", shuntingYard("2 + 2 * 2")); // 2 2 2 * +
+console.log("(2 + 2) * 2 ->", shuntingYard("(2 + 2) * 2")); // 2 2 + 2 *
No results found