练习专区

在构造二叉树时可以按照顺序存储的方式给定结点输入序列，这种方式的二叉树的创建利用了二叉树的性质5：结点编号为i的左孩子和右孩子的编号分别为2i和2i+1。此时给定的二叉树输入序列中用特殊的符号(比如#)代替不存在的结点数据。 除了上述顺序存储的结点输入序列外，二叉树也可以用先序输入序列、中序输入序列或后序输入序列来建立二叉树。但是这些序列建立的二叉树都不唯一，因此，为了用这些序列建立唯一的二叉树，我们通常给定这些序列的扩展序列，也就是扩展形式的二叉树的遍历序列。比如对于有A，B，C构成的满二叉树的先序序列ABC我们可以得到它的扩展先序序列为AB##C##，即在度为0和度为1的结点上加上虚拟结点#来构造扩展的二叉树。 现在，请你编程实现：用给定的扩展二叉树的先序序列来建立二叉树，然后中序遍历该二叉树并输出遍历结果。

输入有多组，每组都是一行字符串，该字符串是扩展二叉树的先序序列。

输出中序遍历的结果

AB##C##
ABD##E##CF##G##
ABC####

BAC
DBEAFCG
CBA