3

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

我的表达式只使用布尔运算符（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 个表达式的 AND 组合的正确后缀表达式是什么？

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

1 回答 1

2

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

于 2015-08-19T15:01:16.237 回答