Я собрал некоторый код для преобразования между постфиксом и инфиксом и обратно. Теперь я пытаюсь взять отдельные постфиксные выражения и объединить их.
В моих выражениях используются только логические операторы (НЕ, 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 )
Я не уверен, является ли это недостатком кода, используемого для объединения выражений, или преобразования постфикса в инфикс.
Каким будет правильное постфиксное выражение для комбинации AND первых 4 выражений выше?
Я подозреваю, что моя проблема в том, что я неправильно обрабатываю оператор НЕ в процедурах преобразования или комбинации (или в обоих).
Ниже приведен код комбинации, за которым следует код преобразования.
Комбинация:
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 <> "!"
