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

您需要做的是概括您​​的代码：目前它假定正好有两个孩子，并且您的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。因此，您无需对两个几乎相同的If ... Else ... End If块进行硬编码，只需将其中一个块放在一个循环中即可。我建议以下内容

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 回答
1

以下应该让您了解如何处理：

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

  1. 取第一个字符，使其成为根节点。使其子节点数为 0。设置当前节点 = 根。

  2. 下一个字符应该是 '('，将在堆栈 rootHistory 上创建的最后一个节点推送。将 '(' 推送到堆栈 newChildren。

  3. 阅读下一个字符。如果是数字，则创建一个新节点。使新节点的子节点数 = 0。将其添加到称为子节点的新节点向量中。每个节点都可以有一个子节点向量。

    结构节点 {
    int 值;
    int numOfChildren;
    向量或节点数组：children[];
    };

  4. 如果上面读取的字符是 ')'，则从 newChildren 堆栈中弹出一个括号。从 rootHistory 中弹出节点，并为其分配最后创建的子向量。

于 2013-09-16T13:08:34.933 回答