Дано бинарное дерево, все его вершины уникально пронумерованы целыми числами.
КЛП-скобочное представление дерева строится следующим образом:
- пустое дерево представляется словом NIL
- дерево из одной вершины представляется одним числом - её номером
- непустое дерево представляется как (n,A,B), где n - номер корня дерева,
A и B - КЛП-скобочные представления левого и правого поддеревьев.
Аналогично строится и ЛКП-представление, только непустое дерево записывается как (A,n,B).
Например, для изображенного на рисунке дерева соответствующие представления имеют вид:
КЛП: (1,(2,4,5),(3,NIL,(6,7,NIL)))
ЛКП: ((4,2,5),1,(NIL,3,(7,6,NIL)))
Дано КЛП-представление дерева. Требуется получить его ЛКП-представление.
Входные данные:
КЛП-представление дерева длиной не более 100000 символов
Выходные данные:
ЛКП-представление этого дерева
Пример входных данных:
(1,(2,4,5),(3,NIL,(6,7,NIL)))
Пример выходных данных:
((4,2,5),1,(NIL,3,(7,6,NIL)))
|
