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.


BEGIN
    # parses s and returns an RPN expression using Dijkstra's "Shunting Yard" algorithm #
    # s is expected to contain a valid infix expression containing single-digit numbers and single-character operators #
    PROC parse = ( STRING s )STRING:
    BEGIN
        # add to the output #
        PROC output element = ( CHAR c )VOID:
        BEGIN
            output[ output pos +:= 1 ] := c;
            output pos +:= 1
        END # output element # ;
        PROC stack op = ( CHAR c )VOID: stack[ stack pos +:= 1 ] := c;
        # unstacks and returns the top operator on the stack - stops the program if the stack is empty #
        PROC unstack = CHAR:
            IF stack pos < 1 THEN
                # empty stack #
                print( ( "Stack underflow", newline ) );
                stop
            ELSE
                # still something on the stack to unstack #
                CHAR    result = stack[ stack pos ];
                stack[ stack pos ] := " ";
                stack pos         -:=  1;
                result
            FI # unstack # ;
        # returns the priority of the operator o - which must be one of "(", "^", "*", "/", "+" or "-" #
        PROC priority of = ( CHAR o )INT: IF o = "(" THEN -1 ELIF o = "^" THEN 4 ELIF o = "*" OR o = "/" THEN 3 ELSE 2 FI;
        # returns TRUE if o is a right-associative operator, FALSE otherwise #
        PROC right = ( CHAR c )BOOL: c = "^";
        PROC lower or equal priority = ( CHAR c )BOOL:
            IF stack pos < 1 THEN FALSE # empty stack #
            ELSE priority of( c ) <= priority of( stack[ stack pos ] )
            FI # lower or equal priority # ;
        PROC lower priority = ( CHAR c )BOOL:
            IF stack pos < 1 THEN FALSE # empty stack #
            ELSE priority of( c ) < priority of( stack[ stack pos ] )
            FI # lower priority # ;
        # max stack size and output size #
        INT    max stack = 32;
        # stack and output queue #
        [ 1 : max stack ]CHAR stack;
        [ 1 : max stack ]CHAR output;
        FOR c pos TO max stack DO stack[ c pos ] := output[ c pos ] := " " OD;
        # stack pointer and output queue pointer #
        INT    stack pos  := 0;
        INT    output pos := 0;
        print( ( "Parsing: ", s, newline ) );
        print( ( "token   output                               stack", newline ) );
        FOR s pos FROM LWB s TO UPB s DO
            CHAR c = s[ s pos ];
            IF c /= " " THEN
                IF c >= "0" AND c <= "9" THEN output element( c )
                ELIF c = "(" THEN stack op( c )
                ELIF c = ")" THEN
                    # close bracket - unstack to the matching "(" and unstack the "(" #
                    WHILE CHAR op char = unstack;
                          op char /= "("
                    DO
                        output element( op char )
                    OD                     
                ELIF right( c ) THEN
                    # right associative operator #
                    WHILE lower priority( c )          DO output element( unstack ) OD;
                    stack op( c )
                ELSE
                    # must be left associative #
                    WHILE lower or equal priority( c ) DO output element( unstack ) OD;
                    stack op( c )
                FI;
                print( ( c, "       ", output, "     ", stack, newline ) )
            FI
        OD;
        WHILE stack pos >= 1 DO output element( unstack ) OD;
        output[ 1 : output pos ]
    END # parse # ;
 
    print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) )
END