问题陈述
你注意到你的好友美泽的生日快到了,于是决定送她一个有根二叉树。 这里,有根二叉树是以下结构。(图 1)
- 每个顶点恰好有一个叫做父亲的顶点,通过边连接。但是,称为根的唯一顶点,例外地没有父亲。
- 上游节点可能恰好有一个称为左孩子的上游节点,或者没有左孩子。如果有左孩子,它通过边与该顶点相连,左孩子的父亲是该顶点。
- 上游节点可能恰好有一个称为右孩子的上游节点,或者没有右孩子。如果有右孩子,它通过边与该顶点相连,右孩子的父亲是该顶点。
图 1. 两个有根二叉树及其合成的例子
你想送手工制品,因此你买了两个市售的带根的二叉树,并将它们叠加合成,从而制作出一个更好的带根二叉树。 你买的这两棵树的每个节点上都写有非负整数。 由于三泽先生喜欢顶点数少而数值大的、性能好的树,所以你决定按照以下步骤来制作新的二叉树。
- 将两棵二叉树各自根节点上写的整数相加,作为新二叉树根节点上写的整数。
- 如果两棵二叉树的根都有左孩子,则以它们为根的二叉树各自合成出一棵二叉树,并作为新二叉树根的左孩子。 如果不是这种情况,新二叉树的根没有左孩子。
- 如果两个二叉树的根都有右子,则用它们各自为根的二叉树合成一个新的二叉树,并作为新二叉树根的右子。否则,新二叉树的根没有右子。
在你实际进行合成作业之前,你决定先确认合成后带根的二叉树将会是什么样子。 给定买来的两个带根的二叉树的信息,请按照上述步骤创建一个程序,求出合成后的新带根二叉树。
这里,带根二叉树的信息用如下格式的字符串表示。
(表示左子树的字符串)[根节点上的整数](表示右子树的字符串)
节点不存在的树用空字符串表示。例如,图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]()