Recursive replacement of matching tags with regular expressions

I have the following string:

<?foo?> <?bar?> <?baz?> hello world <?/?> <?/?> <?/?>

I need a regular expression to convert it into

<?foo?> <?bar?> <?baz?> hello world <?/baz?> <?/bar?> <?/foo?>

The following code works for non-recursive tags:

$x=preg_replace_callback('/.*?<\?\/\?>/',function($x){
    return preg_replace('/(.*<\?([^\/][\w]+)\?>)(.*?)(<\?\/?\?>)/s',
          '\1\3<?/\2?>',$x[0]);
},$str);

You can't do this with regular expressions. You need to write a parser!

So create a stack (an array where you add and remove items from the end. use array_push() array_pop() ).

Iterate through the tags, pushing known opening tags on the stack.

When you come to a closing tag, pop the stack and that will tell you the tag you need to close.

For a recursive structure, make a recursive function. In some form of pseudo-code:

tags = ['<?foo?>', '<?bar?>', '<?baz?>']

// output consumed stream to 'output' and return the rest
function close_matching(line, output) {
  for (tag in tags) {
    if line.startswith(tag) {
      output.append(tag)
      line = close_matching(line.substring(tag.length()), output)
      i = line.indexof('<')
      ... // check i for not found
      output.append(line.substring(0, i))
      j = line.indexof('>')
      ... // check j for error, and check what's between i,j is valid for close tag
      output.append(closetag_for_tag(tag))
      line = line.substring(j + 1)
    }
  }
  return line;
}

This should give you a basic structure that works.