식 (Expressions)

산술식은 보통 연산자를 두 피연산자 사이에 두고 쓰며, 이를 중위 표기법(infix notation) 이라고 한다. 예를 들어 $(x + y) * (z - w)$ 는 중위 표기법으로 쓴 산술식이다. 그러나 식을 계산하는 프로그램을 작성할 때는 식이 후위 표기법(postfix notation, 역폴란드 표기법) 으로 주어지는 편이 더 편리하다. 후위 표기법에서는 연산자를 두 피연산자 뒤에 쓰며, 각 피연산자는 그 자체가 하나의 식일 수 있다. 예를 들어 x y + z w - * 는 위 산술식의 후위 표기이다. 이때는 괄호가 필요하지 않다.

후위 표기식은 스택(stack) 을 이용한 알고리즘으로 계산할 수 있다. 스택은 두 가지 연산을 지원한다.

1. push: 스택의 맨 위에 수를 넣는다.
2. pop: 스택의 맨 위에 있는 수를 꺼낸다.

식을 왼쪽에서 오른쪽으로 훑는다. 수를 만나면 스택에 push 한다. 연산자를 만나면 맨 위의 두 수를 pop 하여 연산을 적용한 뒤 그 결과를 다시 push 한다. 구체적으로, 연산자 $O$ 를 만났을 때의 동작은 다음과 같다.

a := pop();
b := pop();
push(b O a);

식을 모두 처리하고 나면 스택에 남은 단 하나의 수가 결과가 된다.

이제 스택 대신 큐(queue) 를 사용한다고 하자. 큐에도 push 와 pop 이 있지만 그 의미가 다르다.

1. push: 큐의 뒤에 수를 넣는다.
2. pop: 큐의 앞에서 수를 꺼낸다.

주어진 후위 표기식을, 큐를 사용한 같은 알고리즘으로 계산했을 때 원래 식을 스택으로 계산한 결과와 같아지도록 다시 쓰시오.

첫째 줄에 정수 $T$ ($T \le 200$) 가 주어진다. 다음 $T$ 개의 줄에는 각각 후위 표기법으로 된 식이 하나씩 주어진다. 연산자는 대문자로, 수는 소문자로 표현된다. 각 식의 길이는 $10000$ 자 미만이다.

각 식에 대해, 스택 대신 큐를 사용한 알고리즘으로 계산했을 때 같은 결과가 나오는 식을 출력한다. 답을 유일하게 만들기 위해, 연산자가 결합법칙이나 교환법칙을 만족한다고 가정해서는 안 된다.