Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (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 символов.
Для каждой входной строки выведите выражение, результат которого будет таким же, если использовать в алгоритме очередь вместо стека. Чтобы результат определялся однозначно, считайте, что заданные операторы не являются ассоциативными или коммутативными.