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.


with javascript_semantics
bool show_workings = true
 
constant operators  = {"^","*","/","+","-"},
         precedence = { 4,  3,  3,  2,  2 }
 
procedure shunting_yard(string infix, rpn)
    string res = "", sep = "", stack_top 
    sequence stack = {},
             ops = split(substitute_all(infix,{"(",")"},{" ( "," ) "}),' ')
    printf(1,"Infix input: %-32s%s", {infix,iff(show_workings?'\n':' ')})
    for i=1 to length(ops) do
        string op = ops[i]
        if op="(" then
            stack = append(stack,op)
        elsif op=")" then
            while 1 do
                stack_top = stack[$]
                stack = stack[1..$-1]
                if stack_top="(" then exit end if
                res &= sep&stack_top
                sep = " "
            end while
        else
            integer k = find(op,operators)
            if k!=0 then
                integer prec = precedence[k]
                while length(stack) do
                    stack_top = stack[$]
                    k = find(stack_top,operators)
                    if k=0 or prec>precedence[k] 
                          or (prec=precedence[k] and stack_top="^") then
                        exit
                    end if
                    stack = stack[1..$-1]
                    res &= sep&stack_top
                    sep = " "
                end while
                stack = append(stack,op)
            else
                res &= sep&op
                sep = " "
            end if
        end if
        if show_workings then
            ?{op,stack,res}
        end if
    end for
    for i=length(stack) to 1 by -1 do
        string op = stack[i]
        res &= sep&op
        sep = " "
    end for
    printf(1,"result: %-22s [%s]\n", {res,iff(res=rpn?"ok","**ERROR**")})
end procedure
 
shunting_yard("3 + 4 * 2 / (1 - 5) ^ 2 ^ 3","3 4 2 * 1 5 - 2 3 ^ ^ / +")
show_workings = false
shunting_yard("((1 + 2) ^ (3 + 4)) ^ (5 + 6)","1 2 + 3 4 + ^ 5 6 + ^")
shunting_yard("(1 + 2) ^ (3 + 4) ^ (5 + 6)","1 2 + 3 4 + 5 6 + ^ ^")
shunting_yard("((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5","3 4 ^ 2 9 ^ ^ 2 5 ^ ^")
shunting_yard("(1 + 4) * (5 + 3) * 2 * 3","1 4 + 5 3 + * 2 * 3 *")
shunting_yard("1 * 2 * 3 * 4","1 2 * 3 * 4 *")
shunting_yard("1 + 2 + 3 + 4","1 2 + 3 + 4 +")
shunting_yard("(1 + 2) ^ (3 + 4)","1 2 + 3 4 + ^")
shunting_yard("(5 ^ 6) ^ 7","5 6 ^ 7 ^")
shunting_yard("5 ^ 4 ^ 3 ^ 2","5 4 3 2 ^ ^ ^")
shunting_yard("1 + 2 + 3","1 2 + 3 +")
shunting_yard("1 ^ 2 ^ 3","1 2 3 ^ ^")
shunting_yard("(1 ^ 2) ^ 3","1 2 ^ 3 ^")
shunting_yard("1 - 1 + 3","1 1 - 3 +")
shunting_yard("3 + 1 - 1","3 1 + 1 -")
shunting_yard("1 - (2 + 3)","1 2 3 + -")
shunting_yard("4 + 3 + 2","4 3 + 2 +")
shunting_yard("5 + 4 + 3 + 2","5 4 + 3 + 2 +")
shunting_yard("5 * 4 * 3 * 2","5 4 * 3 * 2 *")
shunting_yard("5 + 4 - (3 + 2)","5 4 + 3 2 + -")
shunting_yard("3 - 4 * 5","3 4 5 * -")
shunting_yard("3 * (4 - 5)","3 4 5 - *")
shunting_yard("(3 - 4) * 5","3 4 - 5 *")
shunting_yard("4 * 2 + 1 - 5","4 2 * 1 + 5 -")
shunting_yard("4 * 2 / (1 - 5) ^ 2","4 2 * 1 5 - 2 ^ /")
