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 ShuntingYard(strInfix As String) As String
 
 
  Dim i as Integer
  Dim token, tokenArray() As String
  Dim stack(), queue() As Variant
  Dim discard As String
  Dim op1, op2 As String
 
  Dim Left_Brackets, Right_Brackets As Integer
 
  Dim output As String
  Dim dbl_output As Double
 
 
  Left_Brackets = CountFields(strInfix, "(")
  Right_Brackets = CountFields(strInfix, ")")
 
  If Left_Brackets = Right_Brackets Then
 
 
 
    'Get tokens
    tokenArray = Split(strInfix," ")
 
 
 
    'Initialize array (removed later)
    ReDim stack(1)
    ReDim queue(1)
 
    'Loop over tokens
    For i = 0 to tokenArray.Ubound
 
 
    'i = i + 1
      If i  > UBound(tokenArray) Then
        Exit For
      Else
        token = tokenArray(i ) 'i-1 due to Split returning a Base 0
      End If
      If token = "" Then
        Exit For
      End If
 
 
 
 
 
 
      Dim stackString As String
      Dim queuString As String
 
      for m as Integer = 0 to stack.Ubound
        stackString = stackString +  " " +  stack(m)
      Next
 
      for m as Integer = 0 to queue.Ubound
        queuString = queuString + " " +  queue(m)
      Next
 
      MsgBox(Str(i) + "      " + token + "      " + stackString + "      " + queuString)
 
      'Window1.txtQueu.Text = Window1.txtQueu.Text + Str(i) + "      " + token + "      " + stackString + "      " + queuString + EndOfLIne
 
 
 
 
      ' If-loop over tokens (either brackets, operators, or numbers)
      If token = "(" Then
        stack.Append(token)
 
      ElseIf token = ")" Then
        While stack(stack.Ubound) <> "("
          queue.Append(stack.pop)
        Wend
 
        discard = stack.Pop 'discard "("
      ElseIf isOperator(token) Then
        op1 = token
 
 
        //Do While (isOperator(Peek(stack)))
        While isOperator(    stack(stack.Ubound)  ) = True 
          op2 = stack(stack.Ubound)
          If op2 <> "^" And precedence(op1) = precedence(op2) Then
            '"^" is the only right-associative operator
 
            queue.Append(stack.pop)
 
          ElseIf precedence(op1) < precedence(op2) Then
            queue.Append(stack.Pop)
          Else
            Exit While
          End If
        Wend
        //Loop
 
 
        stack.Append(op1)
      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.Append(CStr(token))
      End If
 
 
 
 
    Next
 
 
 
    for i = 0 to queue.Ubound
      output = output  +queue(i) + " "
    next
 
    for i = stack.Ubound DownTo 0
      output = output + stack(i)+" "
    next
 
 
 
    While InStr(output, "  ") <> 0 
      output = ReplaceAll(output,"  "," ")
    Wend
 
 
    output = Trim(output)
 
 
    Return output
 
  Else
 
    MsgBox("Syntax Error!" + EndOfLine + "Count left brackets: " + Str(Left_Brackets) + EndOfLine +"Count right brackets: " + Str(Right_Brackets))
 
  End If
 
End Function
 
 
Function isOperator(op As String) As Boolean
 
  If InStr("+-*/^", op) <> 0 and Len(op) = 1 Then
    Return True
  End If
 
End Function
 
 
Function precedence(op As String) As Integer
 
  If isOperator(op) = True Then
 
 
 
    If op = "+" or op = "-"  Then  
      Return 2
    ElseIf op = "/" or op = "*" Then
      Return 3
    ElseIf op = "^" Then
      Return 4
    End If
 
 
  End If
 
 
End Function