How to construct a binary tree from a infix string with brackets?

Question

A non-empty tree is defined as {L,a,R}, L is left subtree, and R is Right subtree. {} for subtree is empty. for example, {{{{},3,{}},2,{{},1,{}}},4,{{{},5,{}},6,{}}} constructs an binary tree like the picture.tree constructed from the string

I have found a question for constructs an binary tree from a prefix expression with brackets, but I still have no idea for how to doing this.

Answer 1

I did not get a reply on which data structure or language you expect to use, but here is an implementation of a recursive parser in JavaScript.

It uses a regular expression to tokenise the input into braces and data.

From those tokens it creates instances of a typical Node class.

Finally it outputs that structured tree in a simple, rotated view:

class Node {
    constructor(left, value, right) {
        this.left = left;
        this.value = value;
        this.right = right;
    }
    
    toString() {
        return (this.right ? this.right.toString().replace(/^/gm, "  ") + "\n" : "")
             + this.value
             + (this.left ? "\n" + this.left.toString().replace(/^/gm, "  ") : "");
    }
}

function createTree(s) {
    const tokens = s.matchAll(/,([^{},]+),|[{}]|(.)/g);

    function getToken(expect) {
        let [all, value, error] = tokens.next().value;
        value ||= all;
        if (error || expect && !expect.includes(all)) throw "Unexpected '" + all + "'";
        return value;
    }

    function dfs(readOpening) {
        if (readOpening) getToken("{");
        if (getToken("{}") == "}") return null;
        const node = new Node(dfs(), getToken(), dfs(true));
        getToken("}");
        return node;
    }
    
    return dfs(true);
}

// Demo
const s = "{{{{},3,{}},2,{{},1,{}}},4,{{{},5,{}},6,{}}}";
const root = createTree(s);
console.log(root.toString()); // rotated view, with root at the left