Task

Given the operator characteristics and input from the Shunting-yard algorithm page and tables, use the algorithm to show the changes in the operator stack and RPN output
as each individual token is processed.

 Assume an input of a correct, space separated, string of tokens representing an infix expression
 Generate a space separated output string representing the RPN
 Test with the input string:
  3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3  
 print and display the output here.
 Operator precedence is given in this table:


 operator 
 precedence 
 associativity 
 operation


  ^  
 4 
 right 
 exponentiation


  *  
 3 
 left 
 multiplication


  /  
 3 
 left 
 division


  +  
 2 
 left 
 addition


  -  
 2 
 left 
 subtraction



Extra credit
Add extra text explaining the actions and an optional comment for the action on receipt of each token.



Note
The handling of functions and arguments is not required.



See also

 Parsing/RPN calculator algorithm for a method of calculating a final value from this output RPN expression.
 Parsing/RPN to infix conversion.


function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length = length;
}
 
function push(element) {
  this.dataStore[this.top++] = element;
}
 
function pop() {
  return this.dataStore[--this.top];
}
 
function peek() {
  return this.dataStore[this.top-1];
}
 
function length() {
  return this.top;
}
 
var infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
infix = infix.replace(/\s+/g, ''); // remove spaces, so infix[i]!=" "
 
var s = new Stack();
var ops = "-+/*^";
var precedence = {"^":4, "*":3, "/":3, "+":2, "-":2};
var associativity = {"^":"Right", "*":"Left", "/":"Left", "+":"Left", "-":"Left"};
var token;
var postfix = "";
var o1, o2;
 
for (var i = 0; i < infix.length; i++) {
  token = infix[i];
  if (token >= "0" && token <= "9") { // if token is operand (here limited to 0 <= x <= 9)
    postfix += token + " ";
  }
  else if (ops.indexOf(token) != -1) { // if token is an operator
    o1 = token;
    o2 = s.peek();
    while (ops.indexOf(o2)!=-1 && ( // while operator token, o2, on top of the stack
      // and o1 is left-associative and its precedence is less than or equal to that of o2
      (associativity[o1] == "Left" && (precedence[o1] <= precedence[o2]) ) || 
      // the algorithm on wikipedia says: or o1 precedence < o2 precedence, but I think it should be
      // or o1 is right-associative and its precedence is less than that of o2
      (associativity[o1] == "Right" && (precedence[o1] < precedence[o2])) 
      )){
        postfix += o2 + " "; // add o2 to output queue
        s.pop(); // pop o2 of the stack
        o2 = s.peek(); // next round
    }
    s.push(o1); // push o1 onto the stack
  }
  else if (token == "(") { // if token is left parenthesis
    s.push(token); // then push it onto the stack
  }
  else if (token == ")") { // if token is right parenthesis 
    while (s.peek() != "("){ // until token at top is (
      postfix += s.pop() + " ";
    }
    s.pop(); // pop (, but not onto the output queue
  }
}
postfix += s.dataStore.reverse().join(" ");
print(postfix);