fork download
copy 
  1. s = "A(BB(CC))"
  2. #    012345678
  3.  
  4.  
  5. def build_tree(s, root = {"children": [], "l": 0}, i = 0, j = 0):
  6.   if i == len(s):
  7.     return (root, i)
  8.  
  9.   if s[i] == ")":
  10.     root["r"] = j #root["l"] + 2 * (j - root["l"] + 1)
  11.     return (root, i + 1)
  12.  
  13.   cs = root["children"]
  14.  
  15.   if s[i] == "(":
  16.     if cs and isinstance(cs[-1], list):
  17.       cs[-1][1] = i - 1
  18.       cs[-1][3] = j
  19.     child, ii = build_tree(s, {"children": [], "l": j}, i+1, j)
  20.     root["r"] = child["r"]
  21.     root["children"].append(child)
  22.     return build_tree(s, root, ii, root["r"] + 1)
  23.  
  24.   if not cs or not isinstance(cs[-1], list):
  25.     root["children"].append([i, None, j, None])
  26.  
  27.   root["r"] = j
  28.   return build_tree(s, root, i + 1, j + 1)
  29.  
  30.  
  31. import json
  32.  
  33. print(json.dumps(build_tree(s)[0], indent=2))
Success #stdin #stdout 0.04s 9792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{
  "children": [
    [
      0,
      0,
      0,
      1
    ],
    {
      "children": [
        [
          2,
          3,
          1,
          3
        ],
        {
          "children": [
            [
              5,
              null,
              3,
              null
            ]
          ],
          "l": 3,
          "r": 5
        }
      ],
      "l": 1,
      "r": 6
    }
  ],
  "l": 0,
  "r": 6
}
https://ideone.com/DThEzL
language:
Python 3 (python  3.9.5)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!