Как правильно комбинировать несколько булевых постфиксных выражений?

Question

Я собрал код для преобразования между postfix и infix и обратно. Теперь я пытаюсь взять отдельные постфиксные выражения и объединить их.

Мои выражения используют только логические операторы (NOT, XOR, AND, OR).

Обратите внимание, что числа в выражениях относятся к правилам, которые в конечном итоге получают значение true или false.

В настоящее время у меня возникают проблемы, сочетающие выражения, которые НЕ имеют в них.

Например, я хочу, чтобы объединить следующие в одно выражение постфикса с помощью AND:

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

В настоящее время мой выход за это выглядит следующим образом:

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

Но при преобразовании это инфиксными Я (неправильно) получить (обратите внимание на ведущую &):

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

Я не уверен, что это недостаток кода, используемого для объединения выражений, или от постфикса для преобразования infix.

Какое будет правильное постфиксное выражение для комбинации ANDed из первых 4 выражений выше?

Я подозреваю, что проблема заключается в том, что я неправильно обрабатываю оператор NOT в процедурах преобразования или комбинирования (или обоих).

Ниже приведен код комбинации, а затем код преобразования.

Комбинация:

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 

Конверсия:

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

Здесь изменение кода (в процедуре преобразования), что в результате отмеченного ответа:

Заменить:

If stack.Count <> 0 

С этим:

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

Answer 1

Как указано в комментарии, я считаю, вы должны нажать на выражение обратно в стек, если это унарный оператор, чтобы стать следующей итерации выражение RHS. В противном случае следующий оператор будет рассматриваться как унарный, а также в вашем случае в ведущем &.