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.


import ceylon.collection {
 
	ArrayList
}
 
abstract class Token(String|Integer data) of IntegerLiteral | Operator | leftParen | rightParen {
	string => data.string;
}
class IntegerLiteral(shared Integer integer) extends Token(integer) {}
class Operator  extends Token {
 
	shared Integer precedence;
	shared Boolean rightAssoc;
 
	shared new plus extends Token("+") {
		precedence = 2;
		rightAssoc = false;
	}
	shared new minus extends Token("-") {
		precedence = 2;
		rightAssoc = false;
	}
	shared new times extends Token("*") {
		precedence = 3;
		rightAssoc = false;
	}
	shared new divides extends Token("/") {
		precedence = 3;
		rightAssoc = false;
	}
	shared new power extends Token("^") {
		precedence = 4;
		rightAssoc = true;
	}
 
	shared Boolean below(Operator other) => 
			!rightAssoc && precedence <= other.precedence || rightAssoc && precedence < other.precedence;
}
object leftParen extends Token("(") {}
object rightParen extends Token(")") {}
 
 
shared void run() {
 
	function shunt(String input) {
 
		function tokenize(String input) =>
				input.split().map((String element) => 
					switch(element.trimmed)
					case("(") leftParen
					case(")") rightParen
					case("+") Operator.plus
					case("-") Operator.minus
					case("*") Operator.times
					case("/") Operator.divides
					case("^") Operator.power
					else IntegerLiteral(parseInteger(element) else 0)); // no error handling
 
		value outputQueue = ArrayList<Token>();
		value operatorStack = ArrayList<Token>();
 
		void report(String action) {
			print("``action.padTrailing(22)`` | ``" ".join(outputQueue).padTrailing(25)`` | ``" ".join(operatorStack).padTrailing(10)``");
		}
 
		print("input is ``input``\n");
		print("Action                 | Output Queue              | Operators' Stack
		       -----------------------|---------------------------|-----------------");
 
		for(token in tokenize(input)) {
			switch(token)
			case(is IntegerLiteral) {
				outputQueue.offer(token);
				report("``token`` from input to queue");
			}
			case(leftParen) {
				operatorStack.push(token);
				report("``token`` from input to stack");
			}
			case(rightParen){
				while(exists top = operatorStack.pop(), top != leftParen) {
					outputQueue.offer(top);
					report("``top`` from stack to queue");
				}
			}
			case(is Operator) {
				while(exists top = operatorStack.top, is Operator top, token.below(top)) {
					operatorStack.pop();
					outputQueue.offer(top);
					report("``top`` from stack to queue");
				}
				operatorStack.push(token);
				report("``token`` from input to stack");
			}
		}
		while(exists top = operatorStack.pop()) {
			outputQueue.offer(top);
			report("``top`` from stack to queue");
		}
		return " ".join(outputQueue);
	}
 
	value rpn = shunt("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"); 
	assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +");
	print("\nthe result is ``rpn``");
}