How can I correctly combine multiple boolean postfix expressions?

Question

I've put together some code to convert between postfix and infix and back again. Now I'm trying to take separate postfix expressions and combine them.

My expressions are only using boolean operators (NOT, XOR, AND, OR).

Note that the numbers in the expressions refer to rules which eventually get evaluated to true or false.

At present, I'm experiencing issues combining expressions which have NOT in them.

For example, I want to combine the following into a single postfix expression using AND:

45 46 &
1 !
41 42 | 48 |
50 51 |

Presently my output for this looks like this:

45 46 & 1 ! & 50 51 | & 41 42 | 48 | & 

But when converting this to infix, I (incorrectly) get this (note the leading &):

( ( & ( 45 & 46 ) ! 1 ) & ( 50 | 51 ) ) & ( ( 41 | 42 ) | 48 )

I'm not sure if this is a shortfall of the code used to combine expressions, or of the postfix to infix conversion.

What would be the correct postfix expression for the ANDed combination of the first 4 expressions above?

I suspect my problem is that I am not correctly handling the NOT operator in either the conversion or combination routines (or both).

Combination code is below, followed by conversion code.

Combination:

Public Shared Function GetExpandedExpression(Expressions As List(of String)) As String
    'there is guaranteed to be at least one item in the list.
    ExpandedPostfixExpression = PostfixList(0) & " "
    If PostfixList.Count > 1 Then
        For i As Integer = 1 To PostfixList.Count - 1
            ExpandedPostfixExpression &= PostfixList(i) & " & "
        Next
    End If

    Return ExpandedPostfixExpression.TrimEnd
End Function

Conversion:

Public Class ExpressionConversion

    Private Class Intermediate
        Public expr As String
        Public oper As String
        Public Sub New(expr As String, oper As String)
            Me.expr = expr
            Me.oper = oper
        End Sub
    End Class

    Private Const Operators As String = "!&|*()"

    Private Shared Function IsOperator(elem As String) As Boolean
        Return Operators.Contains(elem)
    End Function

    Public Shared Function PostfixToInfix(postfix As String) As String
        'Adapted from http://www.codeproject.com/Articles/405361/Converting-Postfix-Expressions-to-Infix
        Dim stack = New Stack(Of Intermediate)()
        For Each token As String In postfix.Split(CChar(" "))
            If IsOperator(token) Then
                ' Get the intermediate expressions from the stack.  
                ' If an intermediate expression was constructed using a lower precedent
                ' operator (+ or -), we must place parentheses around it to ensure 
                ' the proper order of evaluation.
                Dim leftExpr As String = ""
                Dim rightExpr As String = ""

                Dim rightIntermediate = stack.Pop()
                If rightIntermediate.oper <> "" AndAlso Precedence(token) >= Precedence(rightIntermediate.oper) Then
                    rightExpr = "( " + rightIntermediate.expr + " )"
                Else
                    rightExpr = rightIntermediate.expr
                End If

                If stack.Count <> 0 Then 'in the case where there is only a unary op eg NOT - skip the following
                    Dim leftIntermediate = stack.Pop()
                    If leftIntermediate.oper <> "" AndAlso Precedence(token) >= Precedence(leftIntermediate.oper) Then
                        leftExpr = "( " + leftIntermediate.expr + " )"
                    Else
                        leftExpr = leftIntermediate.expr
                    End If
                End If
                ' construct the new intermediate expression by combining the left and right 
                ' using the operator (token).
                Dim newExpr = (leftExpr & " " & token & " " & rightExpr).Trim

                ' Push the new intermediate expression on the stack
                stack.Push(New Intermediate(newExpr, token))
            Else
                stack.Push(New Intermediate(token, ""))
            End If
        Next

        ' The loop above leaves the final expression on the top of the stack.
        Return stack.Peek().expr
    End Function

    Private Shared Function Precedence(op As String) As Integer
        Select Case op
            Case "!"
                Return 4
            Case "*"
                Return 3
            Case "&"
                Return 2
            Case "|"
                Return 1
        End Select
        Return 0
    End Function
End Class

UPDATE

Here is the code change (in the conversion routine) that resulted from the marked answer:

Replace this:

If stack.Count <> 0 

With this:

If stack.Count <> 0 And token <> "!"

Answer 1

As stated in the comment, I believe you have to push the expression back onto the stack if it is an unary operator to become next iterations RHS expression. Otherwise the following operator will be treated unary as well resulting in your case in the leading &.