Выражения
Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z - w) - арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w - * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.
Для вычисления выражения, заданного в постфиксной нотации, используется алгоритм, работающий со стеком. Стек - это структура данных, поддерживающая две операции:
push: число кладется на верх стека.
pop: число снимается с вершины стека.
Во время вычисления выражение обрабатывается слева направо. Если приходит число, то кладем его на стек. Если приходит оператор, то извлекаем два числа из стека, применяем к ним оператор и результат кладем обратно в стек. Следующий псевдокод обрабатывает оператор O:
a := pop();
b := pop();
push(b O a);
Результатом выражения будет единственное число, оставшееся в стеке.
Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push и pop, но их смысл немного другой:
push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.
Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?
Входные данные
Первое число содержит число t (t ≤ 200). Каждая из следующих t строк содержит одно выражение в постфиксной записи. Арифметические операции представляются заглавными буквами, числа представляются прописными буквами. Длина каждого выражения менее 10000 символов.
Выходные данные
Для каждой входной строки выведите выражение, результат которого будет таким же, если использовать в алгоритме очередь вместо стека. Чтобы результат определялся однозначно, считайте, что заданные операторы не являются ассоциативными или коммутативными.