← 返回题目列表

AtCoder · jag2016secretspring_c

C. 三泽的有根树

中文机器翻译题面 查看原题

问题陈述

你注意到你的好友美泽的生日快到了,于是决定送她一个有根二叉树。 这里,有根二叉树是以下结构。(图 1)

  • 每个顶点恰好有一个叫做父亲的顶点,通过边连接。但是,称为根的唯一顶点,例外地没有父亲。
  • 上游节点可能恰好有一个称为左孩子的上游节点,或者没有左孩子。如果有左孩子,它通过边与该顶点相连,左孩子的父亲是该顶点。
  • 上游节点可能恰好有一个称为右孩子的上游节点,或者没有右孩子。如果有右孩子,它通过边与该顶点相连,右孩子的父亲是该顶点。

图 1. 两个有根二叉树及其合成的例子

你想送手工制品,因此你买了两个市售的带根的二叉树,并将它们叠加合成,从而制作出一个更好的带根二叉树。 你买的这两棵树的每个节点上都写有非负整数。 由于三泽先生喜欢顶点数少而数值大的、性能好的树,所以你决定按照以下步骤来制作新的二叉树。

  1. 将两棵二叉树各自根节点上写的整数相加,作为新二叉树根节点上写的整数。
  2. 如果两棵二叉树的根都有左孩子,则以它们为根的二叉树各自合成出一棵二叉树,并作为新二叉树根的左孩子。 如果不是这种情况,新二叉树的根没有左孩子。
  3. 如果两个二叉树的根都有右子,则用它们各自为根的二叉树合成一个新的二叉树,并作为新二叉树根的右子。否则,新二叉树的根没有右子。

在你实际进行合成作业之前,你决定先确认合成后带根的二叉树将会是什么样子。 给定买来的两个带根的二叉树的信息,请按照上述步骤创建一个程序,求出合成后的新带根二叉树。

这里,带根二叉树的信息用如下格式的字符串表示。

(表示左子树的字符串)[根节点上的整数](表示右子树的字符串)

节点不存在的树用空字符串表示。例如,图1中合成后形成的新带根二叉树可以 (()[6]())[8](((()[4]())[7]())[9]()) 写成如下形式。


输入

输入以如下格式表示。

$A$
$B$

$A$、$B$ 分别表示购买回来的有根二叉树的信息字符串,长度在 $7$ 到 $1000$ 之间。给定的信息遵循固定格式,不包含多余的空白字符等。同时,不会输入不存在节点的有根树。可以假设每个节点上写的整数在 0 到 1000 之间。但需要注意的是,输出的每个节点上写的整数可能不在这个范围内。

输出

将两个有根二叉树合并后得到的新有根二叉树的信息,请输出为一行。特别注意,不要包含行末换行之外的多余空白字符等。



示例输入 1

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

样本输入 1 的输出

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

示例输入 2

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

样本输入 2 的输出

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

示例输入 3

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

样本输入 3 的输出

()[1110]()

示例输入 4

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

样本输入 4 的输出

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

示例输入 5

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

样本输入 5 的输出

()[1000]()