.net - 如何正确组合多个 bool 后缀表达式？

Question

我整理了一些代码以在后缀和中缀之间相互转换。现在我正在尝试采用单独的后缀表达式并将它们组合起来。

我的表达式仅使用 bool 运算符(NOT、XOR、AND、OR)。

请注意，表达式中的数字指的是最终被评估为真或假的规则。

目前，我在组合不包含在其中的表达式时遇到问题。

例如，我想使用 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 )

我不确定这是用于组合表达式的代码不足，还是后缀到中缀转换的不足。

以上前 4 个表达式的 ANDed 组合的正确后缀表达式是什么？

我怀疑我的问题是我没有在转换或组合例程(或两者)中正确处理 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

更新

这是标记答案导致的代码更改(在转换例程中):

替换这个:

If stack.Count <> 0 

有了这个:

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

Answer 1

如评论中所述，我相信如果表达式是一元运算符才能成为下一次迭代 RHS 表达式，则必须将表达式推回堆栈。否则，以下运算符也将被视为一元运算符，导致您的案例位于前导 & 中。