Reverse tree with braces on Java

Question

There is a tree as String:

R(F,RS,N(43,fd,po,97),100,Y(76,df,TY(R(Y(5,34,23)))),U)

Here, for example: R(), TY() are the nodes. (23, 34, 5) - these are the leaves of a tree.

Need to get:

R(U,Y(TY(R(Y(23,34,5))),df,76),100,N(97,po,fd,43),RS,F)

That is, need to invert the tree. I suppose regular expressions are not suitable here because there are nested brackets. Tried an algorithm based on parenthesis counting:

String newLine = invertLine()

Recursive method invertLine():

private String invertLine(String line) {
    String[] parts = line.split("[(].+[)]"); // separate the node from the vertices
    String head = parts[0];
    String body = line.substring(head.length() + 1, line.length() - 1);
    List<String> elements = new ArrayList<>();
    int startIndexOfElement = 0; // index of the beginning of each element (after the decimal point) 
    int counterBrackets = 0; // variable for counting brackets between commas
    for (int i = 0; i < body.length(); i++) {
        String currentSymbol = Character.toString(body.charAt(i));
        // parenthesis count
        if (currentSymbol.equals("(")) counterBrackets++;
        else if (currentSymbol.equals(")")) counterBrackets--;

        if (counterBrackets == 0) {
            if (currentSymbol.equals(",")) {
                // add current item
                elements.add(body.substring(startIndexOfElement, i));
                startIndexOfElement = i + 1; // next item index
            }
            if (i == body.length() - 1) elements.add(body.substring(startIndexOfElement, i + 1));
        }
    }
    StringBuilder newString = new StringBuilder();
    for (int i = elements.size() - 1; i >= 0; i--) { // vertex writeback 
        // recursive invoke
        if (elements.get(i).contains("(")) elements.set(i, invertLine(elements.get(i)));  
        newString.append(elements.get(i));
        // put a comma after each item except the last
        if (i > 0) newString.append(",");
    }
    // returns a substring with children in reverse order
    return head + "(" + newString.toString() + ")";
}

This algorithm has worked. But I did not pass the test task, and I was not hired. It was a long time ago, but it affected my self-esteem. And I still think maybe there is another way? Maybe here need to use some kind of pattern, for example "composite" pettern, or use a simpler algorithm?

Answer 1

Not sure if this is correct in all cases, but it works on the example input you provided:

static String reverse(String tree)
{
    if(tree.isEmpty()) return "";

    int j=0;
    while(Character.isLetterOrDigit(tree.charAt(j))) j++;

    String node = tree.substring(0, j);

    char treeChar = tree.charAt(j);
    if(treeChar == ')') return node;    

    tree = tree.substring(j+1);

    if(treeChar == '(')
    {
        String children = reverse(tree);                                
        tree = tree.substring(children.length()+1);
        node = String.format("%s(%s)", node, children); 
    }

    String peers = reverse(tree);

    return node.isEmpty() ? peers : peers.isEmpty() ? node : peers + "," + node;
}

Test

System.out.println(reverse("R(F,RS,N(43,fd,po,97),100,Y(76,df,TY(R(Y(5,34,23)))),U)"));

Output

R(U,Y(TY(R(Y(23,34,5))),df,76),100,N(97,po,fd,43),RS,F)