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

Answer 2

Thanks for answerign my question. I finally came up with an naive method by myself. I used recursive function to deal with token and create nodes. It used a counter to judge whether brackets is closed. Here is my code in C++.

createTree(string inp){
    int leftBracket = 0,rightBracket = 0;
    if (inp.length() <= 2) {
        return nullptr;
    }
    else {
        for (int i = 1;;i++) {
            if (leftBracket == rightBracket && inp[i] >= '0' && inp[i] <= '9') {
                treeNode* newNode = new treeNode(inp[i]-'0', createTree(inp.substr(1, i - 2)), createTree(inp.substr(i + 2, inp.length() - i - 3)));
                nodeCounter++;
                return newNode;
            }
            else {
                if (inp[i] == '{') {
                    leftBracket++;
                }
                else if (inp[i] == '}') {
                    rightBracket++;
                }
            }
        }
    }
}