Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

C - みさわさんの根付き木

Problem Statement

あなたは親友であるみさわさんの誕生日が近いことに気づき，根付きの二分木をプレゼントすることにした．
ここで，根付きの二分木とは，以下のようなグラフ構造である．(図 1)

 各頂点には，その頂点の親と呼ばれる頂点がちょうど 1 つだけ存在し，親と辺で結ばれている．ただし，根と呼ばれる 1 つの頂点のみ，例外的に親を持たない．

 各頂点は，左の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．左の子を持つ場合，左の子とは辺で結ばれており，左の子の親はその頂点である．

 各頂点は，右の子と呼ばれる頂点をちょうど1つ持つか，あるいは持たない．右の子を持つ場合，右の子とは辺で結ばれており，右の子の親はその頂点である．

図 1. 2 つの根付きの二分木とその合成の例

あなたは手作りの品を贈りたいと考えたので，市販の根付きの二分木を 2 つ買ってきて重ね合わせて合成することで，さらによい根付きの二分木を 1 つ作ることにした．
あなたが買ってきた 2 つの木の各頂点には非負の整数が書かれている．
みさわさんは少ない頂点数で各数値が大きいような，コストパフォーマンスがよい木が好みなので，以下の手順に沿って新しい二分木を作ることにする．

 2 つの二分木それぞれの根に書かれた整数の和を，新しい二分木の根に書く整数とする．

 どちらの二分木の根も左の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の左の子とする．そうでない場合，新しい二分木の根は左の子を持たない．

 どちらの二分木の根も右の子を持っている場合，それらを根とする二分木それぞれを合成した二分木を作り，新しい二分木の根の右の子とする．そうでない場合，新しい二分木の根は右の子を持たない．

あなたは実際に合成する作業を行う前に，できあがる根付きの二分木がどのようになるのか確かめることにした．
買ってきた 2 つの根付きの二分木の情報が与えられるので，上記の手順に従って合成される新しい根付きの二分木を求めるプログラムを作成せよ．

ここで，根付きの二分木の情報は以下のような形式で文字列として表現するものとする．

(左の子を表す文字列)[根に書かれた整数](右の子を表す文字列)

節点が存在しない木は空文字列とする．例えば図 1 の合成されてできた新しい根付きの二分木は (()[6]())[8](((()[4]())[7]())[9]()) のように書く．

Input

入力は次の形式で表される．

$A$

$B$

$A$，$B$ はそれぞれ買ってきた根付きの二分木の情報を表す文字列であり，長さは $7$ 以上 $1000$ 以下である．
与えられる情報は前述の形式に従っており，余計な空白文字等を含まない．
また，節点が存在しない根付き木が入力されることはない．
各節点に書かれた整数は $0$ 以上 $1000$ 以下であると仮定してよい．
ただし，出力の各節点に書かれる整数はこの範囲に収まらない場合もあることに注意せよ．

Output

2 つの根付きの二分木を合成してできあがる新しい根付きの二分木の情報を 1 行で出力せよ．特に，行末の改行を除く余計な空白文字等を含まないよう注意せよ．

Sample Input 1

((()[8]())[2]())[5](((()[2]())[6](()[3]()))[1]())
(()[4]())[3](((()[2]())[1]())[8](()[3]()))

Output for the Sample Input 1

(()[6]())[8](((()[4]())[7]())[9]())

Sample Input 2

(()[1]())[2](()[3]())
(()[1](()[2]()))[3]()

Output for the Sample Input 2

(()[2]())[5]()

Sample Input 3

(()[1]())[111]()
()[999](()[9]())

Output for the Sample Input 3

()[1110]()

Sample Input 4

(()[2](()[4]()))[8]((()[16]())[32](()[64]()))
((()[1]())[3]())[9](()[27](()[81]()))

Output for the Sample Input 4

(()[5]())[17](()[59](()[145]()))

Sample Input 5

()[0]()
()[1000]()

Output for the Sample Input 5

()[1000]()


Sample input:
((()[8]())[2]())[5](((()[2]())[6](()[3]()))[1]())
(()[4]())[3](((()[2]())[1]())[8](()[3]()))


Sample output:
(()[6]())[8](((()[4]())[7]())[9]())

Submission status: Wrong Answer

Solution code:
in1 = input()
in2 = input()

nodes = [[-1,-1,-1] for _ in range(1000)]
nodes2 = [[-1,-1,-1] for _ in range(1000)]
nodes3 = [[-1,-1,-1] for _ in range(1000)]
def create_node(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            s2 = s[i+5:len(s)-1]
            
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes[cnt][2] = int(s[i+2])
            
            if len(s1) != 0:
                create_node(s1, 2*cnt+1)
                nodes[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node(s2, 2*cnt+2)
                nodes[cnt][1] = 2*cnt+2
            break
            
def create_node2(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            s2 = s[i+5:len(s)-1]
            
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes2[cnt][2] = int(s[i+2])
            
            if len(s1) != 0:
                create_node2(s1, 2*cnt+1)
                nodes2[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node2(s2, 2*cnt+2)
                nodes2[cnt][1] = 2*cnt+2
            break

def print_nodes(i):
    #print(nodes3[i])
    #if nodes3[i][0] == -1 and nodes3[i][1] == -1:
    if nodes3[i][2] == -1:
        return '()'
    return '(' + print_nodes(nodes3[i][0]) + '[' +str(nodes3[i][2])+ ']' + print_nodes(nodes3[i][1]) + ')'

create_node(in1, 0)
create_node2(in2, 0)

for i in range(len(nodes)):
    if nodes[i][2] == -1 or nodes2[i][2] == -1:
        pass
    else:
        nodes3[i][2] = nodes[i][2] + nodes2[i][2]
        nodes3[i][0] = nodes[i][0]
        nodes3[i][1] = nodes[i][1]

#print(nodes3[0:12])
res = print_nodes(0)
print(res[1:len(res)-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = S()
    b = S()

    def f(s):
        if not s:
            return None
        if s[0] != '(':
            return int(s)
        c = 1
        mi = -1
        for i in range(1, len(s)):
            if s[i] == '(':
                c += 1
            elif s[i] == ')':
                c -= 1
                if c == 0:
                    mi = i
                    break

        c = 1
        ki = -1
        for i in range(mi+2, len(s)):
            if s[i] == '[':
                c += 1
            elif s[i] == ']':
                c -= 1
                if c == 0:
                    ki = i
                    break

        return [f(s[mi+2:ki]), f(s[1:mi]), f(s[ki+2:-1])]

    fa = f(a)
    fb = f(b)
    def g(a, b):
        if a is None or b is None:
            return None
        if isinstance(a, int) or isinstance(b, int):
            ai = a
            while not isinstance(ai, int):
                ai = ai[0]

            bi = b
            while not isinstance(bi, int):
                bi = bi[0]

            return ai + bi

        return [g(a[i],b[i]) for i in range(3)]

    def h(a):
        if a is None:
            return ''
        if isinstance(a, int):
            return str(a)
        return '({})[{}]({})'.format(h(a[1]),h(a[0]),h(a[2]))


    return h(g(fa, fb))


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def make_tree(pos, id, S, V, E):
    if S[pos] == ')':
        V[id] = -1
        return pos + 1, id + 1
    par = id
    id += 1
    E[par][0] = id
    pos, id = make_tree(pos + 1, id, S, V, E)
    val = ''
    pos += 1
    while S[pos] != ']':
        val += S[pos]
        pos += 1
    V[par] = int(val)
    pos += 1
    E[par][1] = id
    pos, id = make_tree(pos + 1, id, S, V, E)
    return pos + 1, id

def and_tree(id1, id2, V1, V2, E1, E2):
    if V1[id1] == -1 or V2[id2] == -1:
        return ""
    S = ""
    S += "(" + and_tree(E1[id1][0], E2[id2][0], V1, V2, E1, E2) + ")"
    S += "[" + str(V1[id1] + V2[id2]) + "]"
    S += "(" + and_tree(E1[id1][1], E2[id2][1], V1, V2, E1, E2) + ")"
    return S

S1 = raw_input()
V1 = [-1] * 1000
E1 = [[-1, -1] for i in range(1000)]
make_tree(0, 0, S1, V1, E1)

S2 = raw_input()
V2 = [-1] * 1000
E2 = [[-1, -1] for i in range(1000)]
make_tree(0, 0, S2, V2, E2)

print and_tree(0, 0, V1, V2, E1, E2)

Submission status: Accepted

Solution code:
def parse_node(l, r, S):
    left, right = 0, 0
    cnt = 0
    for i in range(l, r + 1):
        if S[i] == '(':
            cnt += 1
        elif S[i] == ')':
            cnt -= 1
        elif cnt == 0 and S[i] == "[":
            left = i
        elif cnt == 0 and S[i] == "]":
            right = i
    return left, right


def parser(l1, r1, l2, r2):
    n1_l, n1_r = parse_node(l1, r1, S1)
    n2_l, n2_r = parse_node(l2, r2, S2)
    # print(n1_l, n1_r, n2_l, n2_r)
    node = "[{}]".format(int(S1[n1_l + 1:n1_r]) + int(S2[n2_l + 1:n2_r]))
    left_node = "({})".format("" if min(n1_l - l1, n2_l - l2) <= 2 else parser(l1 + 1, n1_l - 2, l2 + 1, n2_l - 2))
    right_node = "({})".format("" if min(r1 - n1_r, r2 - n2_r) <= 2 else parser(n1_r + 2, r1 - 1, n2_r + 2, r2 - 1))
    return left_node + node + right_node



S1, S2 = input(), input()
print(parser(0, len(S1) - 1, 0, len(S2) - 1))

Submission status: Accepted

Solution code:
def convert(S):
    cur = 0
    def parse():
        nonlocal cur
        if S[cur] == ')':
            return ()
        cur += 1 # '('
        left = parse()
        cur += 2 # ')['
        num = 0
        while S[cur] != ']':
            num = 10*num + int(S[cur])
            cur += 1
        cur += 2 # ']('
        right = parse()
        cur += 1 # ')'
        return left, num, right
    return parse()
def dfs(A, B):
    if not A or not B:
        return ()
    return (dfs(A[0], B[0]), [A[1] + B[1]], dfs(A[2], B[2]))
print(str(dfs(convert(input()), convert(input()))).replace(", ","")[1:-1])

Submission status: Accepted

Solution code:
def sToTree(S):
#    print(S)
    if len(S)==0:
        return 'N'
    c = 0
    left=0
    right=0
    #print(S)
    for i in range(len(S)):
        if S[i] =='(':
            c+=1
        elif S[i] ==')':
            c-=1
        elif c==0 and S[i]=='[':
            left=i
        elif c==0 and S[i] ==']':
            right=i
            break
#    print(S[right+1:len(S)-1],right,left)   
    return[sToTree(S[1:left-1]),int(S[left+1:right]),sToTree(S[right+2:len(S)-1])]
    
def dfs(S1,S2):
    if S1=='N' or S2=='N':
        return 'N'

    ret = [dfs(S1[0],S2[0]),S1[1]+S2[1],dfs(S1[2],S2[2])]
    return ret

def my_print(ans):
    if ans == 'N':
        return
    print('(',end='')
    my_print(ans[0])
    print(")[{0}](".format(ans[1]),end = '')
    my_print(ans[2])
    print(')',end='')

S1 = input()
S2 = input()


S1 = sToTree(S1)
S2 = sToTree(S2)

ans = dfs(S1,S2)
my_print(ans)
print()

Submission status: Accepted

Solution code:
class binary_tree():
    def __init__(self,value,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right

def find_corres_bra(s,fr,to):
    count=0 
    x=-1
    for i in range(len(s)):
        if s[i]==fr:
            count += 1
        elif s[i]==to:
            if count==1:
                x=i
                break
            else:
                count-=1
    return x
    

def make_tree(s):
    if s=='':
        return None
    x0=0
    x1=find_corres_bra(s,'(',')')+1
    x2=x1+find_corres_bra(s[x1:],'[',']')+1
    tree=binary_tree(int(s[x1+1:x2-1]),make_tree(s[x0+1:x1-1]),make_tree(s[x2+1:-1]))
    return tree

def synthe_trees(t1,t2):
    tree=binary_tree(value=t1.value+t2.value)
    if t1.left!=None and t2.left !=None:
        tree.left=synthe_trees(t1.left,t2.left)
    if t1.right!=None and t2.right !=None:
        tree.right=synthe_trees(t1.right,t2.right)
    return tree

def tree_to_str(tree):
    if tree==None:
        return ''
    ans='('+ tree_to_str(tree.left)+')'+'['+str(tree.value)+']'+'('+ tree_to_str(tree.right)+')'
    return ans

t1=make_tree(input())
t2=make_tree(input())
tree=synthe_trees(t1,t2)
print(tree_to_str(tree))

Submission status: Accepted

Solution code:
def sep(S):
    l=r=0
    for i,s in enumerate(S):
        l+=s=='('
        r+=s==')'
        if l==r:
            j=S.find(']',i)
            s_l=S[1:i]
            s_r=S[j+2:-1]
            s_c=int(S[i+2:j])
            break
    return s_l,s_c,s_r
def solve(A,B):
    if A=='' or B=='':
        return ''
    a_l,a_c,a_r=sep(A)
    b_l,b_c,b_r=sep(B)
    return '(%s)[%d](%s)'%(solve(a_l,b_l),a_c+b_c,solve(a_r,b_r))
print(solve(input(),input()))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

A = input()
B = input()

A_root = [[-1] * 3 for i in range(1000)]
B_root = [[-1] * 3 for i in range(1000)]

class Source():
  def __init__(self, S):
    self.S = S
    self.pos = 0
   
  
def peek(S):
  return S.S[S.pos] if S.pos < len(S.S) else -1

def next(S):
  S.pos += 1

def tree(S, A, i):
  next(S)
  if peek(S) == ')':
    next(S)
    return -1
  c = i[0]
  i[0] += 1
  l = i[0] 
  left = tree(S, A, i)
  center = root(S, A)
  i[0] += 1
  r = i[0]
  right = tree(S, A, i)
  
  A[c] = [center, l, r]
  next(S)
  
def root(S, A):
  res = 0
  next(S)
  while peek(S) != ']':
    res = res * 10 + int(peek(S))
    next(S)
  next(S)
  
  return res
  
tree(Source('(' + A + ')'), A_root, [0])
tree(Source('(' + B + ')'), B_root, [0])

def f(i, j):
  if A_root[i][0] == -1 or B_root[j][0] == -1:
    return '()'
  center = '[' + str(A_root[i][0] + B_root[j][0]) + ']'
  return '(' + f(A_root[i][1], B_root[j][1]) + center + f(A_root[i][2], B_root[j][2]) + ')'

print(f(0, 0)[1:-1])

Submission status: Runtime Error

Solution code:
def convert(S):
    return eval(S.replace(")[","),[").replace("](","],("))
def dfs(A, B):
    if not A or not B:
        return ()
    return (dfs(A[0], B[0]), [A[1][0] + B[1][0]], dfs(A[2], B[2]))
print(str(dfs(convert(input()), convert(input()))).replace(", ","")[1:-1])

Submission status: Runtime Error

Solution code:
in1 = input()
in2 = input()

nodes = [[-1,-1,-1] for _ in range(1000)]
nodes2 = [[-1,-1,-1] for _ in range(1000)]
nodes3 = [[-1,-1,-1] for _ in range(1000)]


def create_node(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            s2 = s[i+5:len(s)-1]
            
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes[cnt][2] = int(s[i+2])
            
            if len(s1) != 0:
                create_node(s1, 2*cnt+1)
                nodes[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node(s2, 2*cnt+2)
                nodes[cnt][1] = 2*cnt+2
            break
            
def create_node2(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            num = ''
            j = 0
            while s[i+j] != '[':
                j += 1
            #print(s[i+2:i+j+4])
            s2 = s[i+j+5:len(s)-1]
            
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes2[cnt][2] = int(s[i+2:i+j+4])
            
            if len(s1) != 0:
                create_node2(s1, 2*cnt+1)
                nodes2[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node2(s2, 2*cnt+2)
                nodes2[cnt][1] = 2*cnt+2
            break

def print_nodes(i):
    #print(nodes3[i])
    #if nodes3[i][0] == -1 and nodes3[i][1] == -1:
    if nodes3[i][2] == -1:
        return '()'
    return '(' + print_nodes(nodes3[i][0]) + '[' + str(nodes3[i][2]) + ']' + print_nodes(nodes3[i][1]) + ')'

create_node(in1, 0)
create_node2(in2, 0)

for i in range(len(nodes)):
    if nodes[i][2] == -1 or nodes2[i][2] == -1:
        pass
    else:
        nodes3[i][2] = nodes[i][2] + nodes2[i][2]
        nodes3[i][0] = nodes[i][0]
        nodes3[i][1] = nodes[i][1]

# print(nodes[0:12])
# print(nodes2[0:12])
# print(nodes3[0:12])
res = print_nodes(0)
print(res[1:len(res)-1])

Submission status: Runtime Error

Solution code:
in1 = input()
in2 = input()

nodes = [[-1,-1,-1] for _ in range(800)]
nodes2 = [[-1,-1,-1] for _ in range(800)]
nodes3 = [[-1,-1,-1] for _ in range(800)]


def create_node(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            j = 0
            while s[i+j] != ']':
                j += 1
            #print('val:'+ s[i+2:i+j])
            s2 = s[i+j+2:len(s)-1]
            if len(s2) == 1:
                s2 = ''
            #print(s1)
            #print(s2)
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes[cnt][2] = int(s[i+2:i+j])
            
            if len(s1) != 0:
                create_node(s1, 2*cnt+1)
                nodes[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node(s2, 2*cnt+2)
                nodes[cnt][1] = 2*cnt+2
            break

def create_node2(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            j = 0
            while s[i+j] != ']':
                j += 1
            #print(s[i+2:i+j])
            s2 = s[i+j+2:len(s)-1]
            if len(s2) == 1:
                s2 = ''
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes2[cnt][2] = int(s[i+2:i+j])
            
            if len(s1) != 0:
                create_node2(s1, 2*cnt+1)
                nodes2[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node2(s2, 2*cnt+2)
                nodes2[cnt][1] = 2*cnt+2
            break

def print_nodes(i):
    #print(nodes3[i])
    #if nodes3[i][0] == -1 and nodes3[i][1] == -1:
    if nodes3[i][2] == -1:
        return '()'
    return '(' + print_nodes(nodes3[i][0]) + '[' + str(nodes3[i][2]) + ']' + print_nodes(nodes3[i][1]) + ')'

create_node(in1, 0)
create_node2(in2, 0)

for i in range(len(nodes)):
    if nodes[i][2] == -1 or nodes2[i][2] == -1:
        pass
    else:
        nodes3[i][2] = nodes[i][2] + nodes2[i][2]
        nodes3[i][0] = nodes[i][0]
        nodes3[i][1] = nodes[i][1]

# print(nodes[0:12])
# print(nodes2[0:12])
# print(nodes3[0:12])
res = print_nodes(0)
print(res[1:len(res)-1])

Submission status: Runtime Error

Solution code:
in1 = input()
in2 = input()

nodes = [[-1,-1,-1] for _ in range(100000)]
nodes2 = [[-1,-1,-1] for _ in range(100000)]
nodes3 = [[-1,-1,-1] for _ in range(100000)]


def create_node(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            j = 0
            while s[i+j] != ']':
                j += 1
            #print('val:'+ s[i+2:i+j])
            s2 = s[i+j+2:len(s)-1]
            if len(s2) == 1:
                s2 = ''
            #print(s1)
            #print(s2)
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes[cnt][2] = int(s[i+2:i+j])
            
            if len(s1) != 0:
                create_node(s1, 2*cnt+1)
                nodes[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node(s2, 2*cnt+2)
                nodes[cnt][1] = 2*cnt+2
            break

def create_node2(s, cnt):
    
    #print('s: ' + s)
    cnt_l = 0
    cnt_r = 0
    for i in range(len(s)):
        if s[i] == '(':
            cnt_l += 1
        elif s[i] == ')':
            cnt_r += 1
        if cnt_l == cnt_r and cnt_l != 0:
            s1 = s[1:i]
            j = 0
            while s[i+j] != ']':
                j += 1
            #print(s[i+2:i+j])
            s2 = s[i+j+2:len(s)-1]
            if len(s2) == 1:
                s2 = ''
            #print(cnt, 's1:'+s1, 's2:'+ s2, 's[i+2]:' + s[i+2])
            nodes2[cnt][2] = int(s[i+2:i+j])
            
            if len(s1) != 0:
                create_node2(s1, 2*cnt+1)
                nodes2[cnt][0] = 2*cnt+1
            if len(s2) != 0:
                create_node2(s2, 2*cnt+2)
                nodes2[cnt][1] = 2*cnt+2
            break

def print_nodes(i):
    #print(nodes3[i])
    #if nodes3[i][0] == -1 and nodes3[i][1] == -1:
    if nodes3[i][2] == -1:
        return '()'
    return '(' + print_nodes(nodes3[i][0]) + '[' + str(nodes3[i][2]) + ']' + print_nodes(nodes3[i][1]) + ')'

create_node(in1, 0)
create_node2(in2, 0)

for i in range(len(nodes)):
    if nodes[i][2] == -1 or nodes2[i][2] == -1:
        pass
    else:
        nodes3[i][2] = nodes[i][2] + nodes2[i][2]
        nodes3[i][0] = nodes[i][0]
        nodes3[i][1] = nodes[i][1]

# print(nodes[0:12])
# print(nodes2[0:12])
# print(nodes3[0:12])
res = print_nodes(0)
print(res[1:len(res)-1])