2

文字列からマルチツリーを解析しようとしています。

構文:

ルート(ツリー、ツリー、ツリー ...) =

ここに画像の説明を入力

例えば ​​：

1(2,3,4(5,3),4(7,8,5)) =

ここに画像の説明を入力

文字列から二分木を解析する方法を見つけました。

私のコード：

Public Class Tree
Public l As Tree = Nothing
Public r As Tree = Nothing
Public value As String
Public Sub New(ByVal Str As String)
    If Str = "" Then Throw New Exception("Input String is Nothing ("""")")
    Dim Error_Report As String = RunCheck(Str)
    If Not Error_Report = "" Then Throw New Exception(Error_Report)
    If Str.Contains("(") Then
        Try
            value = Str.Substring(0, Str.IndexOf("("))
            BulidTreeByInTo(Str.Substring(Str.IndexOf("(") + 1, Str.Length - 2 - Str.IndexOf("(")), l, r)
        Catch ex As Exception
            Throw ex
        End Try
    Else
        value = Str
    End If
End Sub
Private Function RunCheck(ByVal str As String) As String
    Dim Open_Close As Integer = 0
    For i = 0 To str.Length - 1 Step 1
        If str(i).ToString = "(" Then
            Open_Close += 1
        ElseIf str(i).ToString = ")" Then
            Open_Close -= 1
        End If
        If i >= 1 Then
            If (str(i - 1).ToString = ")" And str(i).ToString = "(") Or (str(i - 1).ToString = "(" And str(i).ToString = ")") Then
                Return "Error in bracket At Index " & i
            End If
            If (str(i - 1).ToString = "(" And str(i).ToString = ",") Or (str(i - 1).ToString = "," And str(i).ToString = ")") Or (str(i - 1).ToString = "," And str(i).ToString = "(") Or (str(i - 1).ToString = "," And str(i).ToString = ",") Then
                Return "Error in Comma At Index " & i
            End If
        End If
    Next
    If Not Open_Close = 0 Then Return "Not all existing brackets are Closed"
    Return ""
End Function
Private Function GetTheSameLevel(ByVal s As String) As Integer
    Dim level As Integer = 0
    For i = 0 To s.Length - 1 Step 1
        If s(i).ToString = "," And level = 0 Then
            Return i
        End If
        If s(i).ToString = "(" Then
            level += 1
        End If
        If s(i).ToString = ")" Then
            level -= 1
        End If
    Next
    Return -1
End Function
Private Sub BulidTreeByInTo(ByVal str As String, ByRef l1 As Tree, ByRef r1 As Tree)
    Dim MiddleIndex As Integer = GetTheSameLevel(str)
    Dim p1 As String = str.Substring(0, MiddleIndex)
    Dim p2 As String = str.Substring(MiddleIndex + 1, str.Length - 1 - MiddleIndex)
    Try
        If p1.Contains("(") Then
            If Not p1.Substring(0, p1.IndexOf("(")).ToString = "\" Then
                l1 = New Tree(p1.Substring(0, p1.IndexOf("(")))
                BulidTreeByInTo(p1.Substring(p1.IndexOf("(") + 1, p1.Length - 2 - p1.IndexOf("(")), l1.l, l1.r)
            End If
        Else
            If Not p1 = "\" Then
                l1 = New Tree(p1)
            End If
        End If
        If p2.Contains("(") Then
            If Not p2.Substring(0, p2.IndexOf("(")).ToString = "\" Then
                r1 = New Tree(p2.Substring(0, p2.IndexOf("(")))
                BulidTreeByInTo(p2.Substring(p2.IndexOf("(") + 1, p2.Length - 2 - p2.IndexOf("(")), r1.l, r1.r)
            End If
        Else
            If Not p2 = "\" Then
                r1 = New Tree(p2)
            End If
        End If
    Catch ex As Exception
        Throw ex
    End Try
End Sub
End Class
4

2 に答える 2

2

あなたがする必要があるのは、コードを一般化することです: 現時点では、正確に 2 つの子を想定しており、Treeクラスにはフィールドがあります。

Public l As Tree = Nothing
Public r As Tree = Nothing

しかし、各ツリーが持つ子の数がわからないため、コレクションが必要です:Listは妥当な選択です

Public children As List(Of Tree) = New List(Of Tree)

これは空に初期化されていることに注意してください。発見したら、子を追加する必要があります。

次に、文字列を解析して子を見つけるコードを確認する必要があります。現時点では、関数があります

Private Sub BulidTreeByInTo(ByVal str As String, ByRef l1 As Tree, ByRef r1 As Tree)

これは次のように変更する必要があります

Private Sub BulidTreeByInTo(ByVal str As String, ByRef ch As List(Of Tree))

最後にBulidTreeByInTo、ループを使用して必要な数の子を に追加するように、 の実装を変更する必要がありchます。したがって、2 つのほぼ同一のIf ... Else ... End Ifブロックをハードコーディングするのではなく、これらのブロックの 1 つだけをループに含める必要があります。次の行に沿って何かを提案します

Do
    Dim MiddleIndex As Integer = GetTheSameLevel(str) ' find comma at same level
    Dim p1 As String = str.Substring(0, MiddleIndex) ' substring up to this comma
    ' str is rest of string past the comma, which can be 0 or more children
    str = str.Substring(MiddleIndex + 1, str.Length - 1 - MiddleIndex)
    Try
        If p1.Contains("(") Then
            If Not p1.Substring(0, p1.IndexOf("(")).ToString = "\" Then
                ch.Add(New Tree(p1.Substring(0, p1.IndexOf("("))))
                BulidTreeByInTo(p1.Substring(p1.IndexOf("(") + 1, p1.Length - 2 - p1.IndexOf("(")), l1.ch)
            End If
        Else
            If Not p1 = "\" Then
                ch.Add(New Tree(p1))
            End If
        End If
    Catch ex As Exception
        Throw ex
    End Try
While MiddleIndex >= 0

GetTheSameLevel関数が同じレベルで次のコンマ<0を見つけ、コンマが見つからない場合は戻るように見えます<0。ループ終了条件も同様です。アイデアは、既存のコードのほとんどを保持し、右側の文字列としてではなくp2、右側の文字列を に再割り当てするというものstrです。ループを通過するたびに、 から次のビットを切り取って にstr代入しp1ます。

私は VB プログラマーではないので、これをコンパイルしたりテストしたりしていません。

于 2013-09-16T13:47:17.473 に答える