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.   cs = root["children"]
  10.  
  11.   if s[i] == ")":
  12.     if cs and isinstance(cs[-1], list):
  13.       cs[-1][1] = i - 1
  14.       cs[-1][3] = j - 1
  15.     root["r"] = root["l"] + 2 * (j - root["l"]) - 1
  16.     return (root, i + 1)
  17.  
  18.   if s[i] == "(":
  19.     if cs and isinstance(cs[-1], list):
  20.       cs[-1][1] = i - 1
  21.       cs[-1][3] = j - 1
  22.     child, next_i, = build_tree(s, {"children": [], "l": j}, i+1, j)
  23.     root["r"] = child["r"]
  24.     root["children"].append(child)
  25.     return build_tree(s, root, next_i, root["r"] + 1)
  26.  
  27.   if not cs or not isinstance(cs[-1], list):
  28.     root["children"].append([i, None, j, None])
  29.  
  30.   root["r"] = j
  31.   return build_tree(s, root, i + 1, j + 1)
  32.  
  33.  
  34. def query(s, root, l, r):
  35.   out = ""
  36.   for child in root["children"]:
  37.     if isinstance(child, list):
  38.       # leaf starts at or after l
  39.       if l <= child[2] <= r:
  40.         out += s[child[0]:child[1] + 1 - max(0, child[3] - r)]
  41.       # leaf starts before l
  42.       elif child[2] < l <= child[3]:
  43.         out += s[child[0] + l - child[2]:child[1] + 1]
  44.     # parenthetical starts after r
  45.     elif child["l"] > r:
  46.       return out
  47.     # parenthetical ends before l
  48.     elif child["r"] < l:
  49.       continue
  50.     else:
  51.       stored_r = child["l"] + (child["r"] - child["l"]) // 2
  52.       print((l, stored_r, child))
  53.       out += query(s, child, l, min(stored_r, r))
  54.       if r >= stored_r:
  55.         out += query(s, child, max(l, child["l"]), stored_r)
  56.   return out
  57.  
  58. import json
  59.  
  60. root, i = build_tree(s)
  61.  
  62. print(query(s, root, 3, 8))
  63.  
  64. print(json.dumps(root, indent=2))
Success #stdin #stdout 0.03s 9776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(3, 6, {'children': [[2, 3, 1, 2], {'children': [[5, 6, 3, 4]], 'l': 3, 'r': 6}], 'l': 1, 'r': 12})
(3, 4, {'children': [[5, 6, 3, 4]], 'l': 3, 'r': 6})
(3, 4, {'children': [[5, 6, 3, 4]], 'l': 3, 'r': 6})
CCCCCCCC
{
  "children": [
    [
      0,
      0,
      0,
      0
    ],
    {
      "children": [
        [
          2,
          3,
          1,
          2
        ],
        {
          "children": [
            [
              5,
              6,
              3,
              4
            ]
          ],
          "l": 3,
          "r": 6
        }
      ],
      "l": 1,
      "r": 12
    }
  ],
  "l": 0,
  "r": 12
}
https://ideone.com/E1IeLF
language:
Python 3 (python  3.9.5)
created:
1 day 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!