Задача №3352. Дерево разбора (A)
Арифметические выражения, использующие сложение, вычитание, умножение, деление и возведение в степень определяются следующей грамматикой:
<выражение> -> <слагаемое> | <выражение> + <слагаемое> | <выражение> - <слагаемое>
<слагаемое> -> <множитель> | <слагаемое> \(\times\) <множитель> | <слагаемое> / <множитель>
<множитель> -> <элемент> | <элемент> ^ <множитель>
<элемент> -> <переменная> | (<выражение>)
<переменная> -> a | b | ... | z
Сложение, вычитание, умножение и деление левоассоциативны, а возведение в степень правоассоциативно.
Для арифметического выражения определено его дерево разбора. Это двоичное дерево, в котором внутренние узлы соответствуют бинарным операциям, а листья соответствуют переменным. Дерево строится рекурсивно.
- Дерево для переменной — это дерево из одной вершины, в которой записана эта переменная.
- Дерево для элемента, являющегося выражением в скобках, — это дерево для самого выражения.
- Дерево для множителя, являющегося элементом, — это дерево для этого элемента. Дерево для множителя вида «элемент e, возведенный в степень “множитель f”» — это дерево, в котором в корне записана операция ‘^’, левое поддерево корня — дерево для элемента e, правое поддерево корня — дерево для множителя f.
- Деревья для множителя и слагаемого определяются аналогично, с тем лишь различием, что соответствующие операции лево-ассоциативные.
Во входном файле содержится корректное арифметическое выражение, состоящее не более чем из 400 символов.
В выходной файл выведите дерево разбора. Дерево разбора для переменной должно быть размера \(1\times 1\) и содержать эту переменную. Дерево, в корне которого записана операция, с поддеревьями \(T_1\) и \(T_2\), которые имеют размеры \(h_1\times w_1\) и \(h_2 \times w_2\) соответственно, должно быть размера \((max [h_1; h_2] + 2) \times (w_1 + w_2 + 5)\). Подробнее о формате вывода можно узнать, изучив пример выходного файла (см. ниже). Следует использовать следующие вспомогательные символы: минус ‘-’ (код ASCII 45), точка ‘.’ (код ASCII 46), вертикальная черта ‘|’ (код ASCII 124), квадратные скобки ‘[’ и ‘]’ (коды ASCII 91 and 93).
(a+b+c)*(d-a)
.----[*]----.
| |
.----[+]-. .-[-]-.
| | | |
.-[+]-. c d a
| |
a b