Recursive searching a pattern in a string

Question

I am using c#. I have following string

<li> 
    <a href="abc">P1</a> 
    <ul>
        <li><a href = "bcd">P11</a></li>
        <li><a href = "bcd">P12</a></li>
        <li><a href = "bcd">P13</a></li>
        <li><a href = "bcd">P14</a></li>
    </ul>
</li>
<li> 
    <a href="abc">P2</a> 
    <ul>
        <li><a href = "bcd">P21</a></li>
        <li><a href = "bcd">P22</a></li>
        <li><a href = "bcd">P23</a></li>
    </ul>
</li>
<li> 
    <a href="abc">P3</a> 
    <ul>
        <li><a href = "bcd">P31</a></li>
        <li><a href = "bcd">P32</a></li>
        <li><a href = "bcd">P33</a></li>
        <li><a href = "bcd">P34</a></li>
    </ul>
</li>
<li> 
    <a href="abc">P4</a> 
    <ul>
        <li><a href = "bcd">P41</a></li>
        <li><a href = "bcd">P42</a></li>
    </ul>
</li>

My aim is to fill the following list from the above string.

List<class1>

class1 has two properties,

string parent;
List<string> children;

It should fill P1 in parent and P11,P12,P13,P14 in children, and make a list of them.

Any suggestion will be helpful.

Edit

Sample

public List<class1> getElements()
{
    List<class1> temp = new List<class1>();
    foreach(// <a> element in string)
    {
        //in the recursive loop
        List<string> str = new List<string>();
        str.add("P11");
        str.add("P12");
        str.add("P13");
        str.add("P14");

        class1 obj = new class1("P1",str);
        temp.add(obj);
    }
    return temp;
}

the values are hard coded here, but it would be dynamic.

That's work for [**`Html Agility Pack`**](http://htmlagilitypack.codeplex.com/). — Tim Schmelter, Nov 30 '12 at 13:20
@tim: I am getting code of generated html page of .aspx file by javascript and storing it in hiddenfield. Then It would be available to me in backend as string **sorry No webrowser control** — RTRokzzz, Nov 30 '12 at 13:25
Could you pelase elaborate on what exactly you want as the strings in the list you are wanting to fill? So an example of 'class1' could have parent == "P1" and children = ["P11", "P22", ...]? What is supposed to be in the list? Only the links, right? Are the lists going to be nested any more (ie. P222 etc?) — K.L., Nov 30 '12 at 13:44
@K.L. : I just want data in children list i.e. P11,P12,.. and so on, not the values of links. You can assume it similar to innerHtml. — RTRokzzz, Nov 30 '12 at 13:49
still not clear to me. Could you edit the question and show us a sample (say for P1) of the expected result list? Also, you didnt say if you wanted the algorithm to work for any number of nesting levels, or just the 2, like in your example. Its kinda confusing, cause in this sort of task, youd expect a TREE, not a list! — K.L., Nov 30 '12 at 14:02
@K.L. please see the edit. Sorry boss, If you know any of the way to convert string in HtmlElementCollection, then I can solve it. — RTRokzzz, Nov 30 '12 at 14:11
You can download [Html Agility Pack](http://htmlagilitypack.codeplex.com/) from nuget, it will add a dll to your project as a reference, there is plenty of documentation out there — CR41G14, Nov 30 '12 at 13:24

score 4 · Answer 1 · answered Nov 30 '12 at 14:05

What you want is a recursive descent parser. All the other suggestions of using libraries are basically suggesting that you use a recursive descent parser for HTML or XML that has been written by others.

The basic structure of a recursive descent parser is to do a linear search of a list of tokens (in your case a string) and upon encountering a token that delimits a sub entity call the parser again to process the sublist of tokens (substring).

You can Google for the term "recursive descent parser" and find plenty of useful result. Even the Wikipedia article is fairly good in this case and includes an example of a recursive descent parser in C.

Tim Schmelter · Accepted Answer · 2012-11-30T14:29:47.783

3

If you can't use a third party tool like my recommended Html Agility Pack you could use the Webbrowser class and the HtmlDocument class to parse the HTML:

WebBrowser wbc = new WebBrowser();
wbc.DocumentText = "foo"; // necessary to create the document
HtmlDocument doc = wbc.Document.OpenNew(true);
doc.Write((string)html); // insert your html-string here
List<class1> elements = wbc.Document.GetElementsByTagName("li").Cast<HtmlElement>()
    .Where(li => li.Children.Count == 2)
    .Select(outerLi => new class1
    {
        parent = outerLi.FirstChild.InnerText,
        children = outerLi.Children.Cast<HtmlElement>()
            .Last().Children.Cast<HtmlElement>()
            .Select(innerLi => innerLi.FirstChild.InnerText).ToList()
    }).ToList();

Here's the result in the debugger window:

enter image description here

edited Nov 30 '12 at 14:29

answered Nov 30 '12 at 14:07

Tim Schmelter

450,073
74
686
939

I tried your code, but unfortunately it is showing following error **ActiveX control '8856f961-340a-11d0-a96b-00c04fd705a2' cannot be instantiated because the current thread is not in a single-threaded apartment.** – RTRokzzz Nov 30 '12 at 14:54
@user1866361: Is this a console application? It seems that this will solve the problem: http://stackoverflow.com/q/5519294/284240 `Webbrowser` is a `Winforms` class. – Tim Schmelter Nov 30 '12 at 15:09

score 1 · Answer 3 · answered Nov 30 '12 at 14:27

You can also use XmlDocument:

XmlDocument doc = new XmlDocument();
doc.LoadXml(yourInputString);
XmlNodeList colNodes = xmlSource.SelectNodes("li");
foreach (XmlNode node in colNodes)
{
    // ... your logic here
    // for example
    // string parentName = node.SelectSingleNode("a").InnerText;
    // string parentHref = node.SelectSingleNode("a").Attribures["href"].Value;
    // XmlNodeList children = 
    //       node.SelectSingleNode("ul").SelectNodes("li");
    // foreach (XmlNode child in children)
    // {
    //         ......
    // }
}

Recursive searching a pattern in a string

3 Answers3