regex for proper nesting of dynamic menu

Question

I've a dynamic menu which looks like

<li class='has-sub'> cat1</li>
<ul>
    <li> test5</li>
    <li class='has-sub'> cat2</li>
    <ul>
        <li> cat9</li>
        <li class='has-sub'> cat7</li>
        <ul>
            <li> cat8</li>
            <li> cat10</li>
            <li> cat1 cat2</li>
        </ul>
    </ul>
</ul>
<li class='has-sub'> cat3</li>
<ul>
    <li> cat5</li>
</ul>

I want to change that to a properly nested navigation menu like

<li class='has-sub'> <a href='#'><span>cat1</span></a>
<ul>
    <li><a href='#'><span> test5</span></a></li>
    <li class='has-sub'><a href='#'><span> cat2</span></a>
    <ul>
        <li> <a href='#'><span>cat9</span></a></li>
        <li class='has-sub'> <a href='#'><span>cat7</span></a>
        <ul>
            <li> <a href='#'><span>cat8</span></a></li>
            <li> <a href='#'><span>cat10</span></a></li>
            <li> <a href='#'><span>cat1 cat2</span></a></li>
        </ul>
        </li>
    </ul>
    </li>
</ul>
</li>
<li class='has-sub'> <a href='#'><span>cat3</span></a>
<ul>
    <li> <a href='#'><span>cat5</span></a></li>
</ul>
</li>

I tried few str_replace but since the list is dynamic It wont work. I'm new to Regex and am not sure how to format this dynamic menu to a properly nested/formatted menu.

Thanks in advance!

Answer 1

A simple DOM Parser and an strtr() will solve this...

$dom = new DOMDocument;
$dom->loadHTML($html);
$arrLi = array();
foreach ($dom->getElementsByTagName('li') as $tag) {
  $arrLi[$tag->nodeValue]="<a href='#'><span>$tag->nodeValue</span></a>";
}
echo $html = strtr($html,$arrLi);

Demonstration

Answer 2

It's an answer that has been linked to more than it probably has been read, but still: You can't parse markup using regex. Not reliably anyway.
Instead, you should use a parser like the DOMDocument class. Basic usage here would be:

$dom = new DOMDocument();
$dom->loadHTML($theMarkupString);
//get the list:
$list = $dom->getElementById('navContainerID');
$navItems = $list->getElementsByTagName('li');
foreach($navItems as $item)
{
    //add spans, links, classes... how to do so is all in the doc pages
}