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.


Option Explicit
Option Base 1
 
Function ShuntingYard(strInfix As String) As String
Dim i As Long, j As Long, token As String, tokenArray() As String
Dim stack() As Variant, queue() As Variant, discard As String
Dim op1 As String, op2 As String
 
Debug.Print strInfix
 
' Get tokens
tokenArray = Split(strInfix)
 
' Initialize array (removed later)
ReDim stack(1)
ReDim queue(1)
 
' Loop over tokens
Do While 1
    i = i + 1
    If i - 1 > UBound(tokenArray) Then
        Exit Do
    Else
        token = tokenArray(i - 1) 'i-1 due to Split returning a Base 0
    End If
    If token = "" Then: Exit Do
 
    ' Print
    Debug.Print i, token, Join(stack, ","), Join(queue, ",")
    ' If-loop over tokens (either brackets, operators, or numbers)
    If token = "(" Then
        stack = push(token, stack)
    ElseIf token = ")" Then
        While Peek(stack) <> "("
            queue = push(pop(stack), queue)
        Wend
        discard = pop(stack) 'discard "("
    ElseIf isOperator(token) Then
        op1 = token
        Do While (isOperator(Peek(stack)))
'            Debug.Print Peek(stack)
            op2 = Peek(stack)
            If op2 <> "^" And precedence(op1) = precedence(op2) Then
                '"^" is the only right-associative operator
                queue = push(pop(stack), queue)
            ElseIf precedence(op1$) < precedence(op2$) Then
                queue = push(pop(stack), queue)
            Else
                Exit Do
            End If
        Loop
        stack = push(op1, stack)
    Else   'number
        'actually, wrong operator could end up here, like say %
        'If the token is a number, then add it to the output queue.
        queue = push(CStr(token), queue)
    End If
Loop
 
While stack(1) <> ""
    If Peek(stack) = "(" Then Debug.Print "no matching ')'": End
    queue = push(pop(stack), queue)
Wend
 
' Print final output
ShuntingYard = Join(queue, " ")
Debug.Print "Output:"
Debug.Print ShuntingYard
End Function
 
'------------------------------------------
Function isOperator(op As String) As Boolean
    isOperator = InStr("+-*/^", op) <> 0 And Len(op$) = 1
End Function
 
Function precedence(op As String) As Integer
    If isOperator(op$) Then
        precedence = 1 _
            - (InStr("+-*/^", op$) <> 0) _
            - (InStr("*/^", op$) <> 0) _
            - (InStr("^", op$) <> 0)
    End If
End Function
 
'------------------------------------------
Function push(str, stack) As Variant
Dim out() As Variant, i As Long
If Not IsEmpty(stack(1)) Then
    out = stack
    ReDim Preserve out(1 To UBound(stack) + 1)
    out(UBound(out)) = str
Else
    ReDim out(1 To 1)
    out(1) = str
End If
push = out
End Function
 
Function pop(stack)
pop = stack(UBound(stack))
If UBound(stack) > 1 Then
    ReDim Preserve stack(1 To UBound(stack) - 1)
Else
    stack(1) = ""
End If
End Function
 
Function Peek(stack)
    Peek = stack(UBound(stack))
End Function