3

後置と中置の間で変換し、再び元に戻すコードをいくつかまとめました。今、私は別々の後置式を取り、それらを結合しようとしています。

私の式はブール演算子 (NOT、XOR、AND、OR) のみを使用しています。

式の数字は、最終的に true または false に評価されるルールを参照していることに注意してください。

現在、NOT を含む式を組み合わせると問題が発生します。

たとえば、AND を使用して、次を 1 つの後置式に結合したいと考えています。

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 に答える