Uva 11234 Expressions(이차 트리 계층 이동)

Problem E: Expressions
Arithmetic expressions are usually written with the operators in between the two operands (which is called infix notation).
두 조작수 사이에는 연산자 (이른바 접미사) 가 끼어 있다.
For example, (x+y)*(z-w) is an arithmetic expression in infix notation.
예를 들어, (X+Y)*(Z-W)는 접미사입니다.
However, it is easier to write a program to evaluate an expression if the expression is written in postfix notation (also known as reverse polish notation).
그러나 접미사식(역폴란드식)을 사용하면 표현식의 결과를 계산하기 위한 프로그램을 작성하기 쉽다.
In postfix notation, an operator is written behind its two operands, which may be expressions themselves.
접두사에서 조작부호는 표현식 자체의 뒤에 두 개의 조작수를 기록합니다.
For example, x y + z w - * is a postfix notation of the arithmetic expression given above. Note that in this case parentheses are not required.
예를 들어 XY+ZW-*는 위에서 설명한 산술 표현식의 접두사 표현법입니다.
이 경우에는 괄호가 필요 없습니다.
To evaluate an expression written in postfix notation, an algorithm operating on a stack can be used.
접두사를 평가하기 위해 창고 작업의 알고리즘을 모두 사용할 수 있다.
A stack is a data structure which supports two operations:
스택은 두 가지 작업을 지원하는 데이터 구조입니다.
    push: a number is inserted at the top of the stack. push: 숫자를 창고 꼭대기에 눌러 넣기
    pop: the number from the top of the stack is taken out.
pop:창고 꼭대기에서 숫자를 팝업합니다
During the evaluation, we process the expression from left to right.
우리는 왼쪽에서 오른쪽까지의 표현을 처리한다.
If we encounter a number, we push it onto the stack.
만약 우리가 숫자를 만났다면, 우리는 그것을 창고에 눌러 넣어야 한다
If we encounter an operator, we pop the first two numbers from the stack, apply the operator on them, and push the result back onto the stack. 만약 우리가 연산자를 만났다면, 우리는 창고에서 두 개의 숫자를 꺼내서 연산을 거친 후에 결과를 창고로 밀어넣어야 한다.
More specifically, the following pseudocode shows how to handle the case when we encounter an operator O: 더 구체적으로 말하자면 아래의 위조 코드는 어떻게 처리하는지 보여주는 상황에서 우리가 조작부호 O를 만났을 때
a := pop();//팝업 a
b := pop();//팝업 b
push(b O a);//b O a를 창고에 눌러넣기
The result of the expression will be left as the only number on the stack.
표현식의 결과는 창고에 보존됩니다.
Now imagine that we use a queue instead of the stack. 이제 창고를 하나의 대기열로 바꾸는 것을 상상해 보세요.
A queue also has a push and pop operation, but their meaning is different:
대기열도push와pop이 있지만 창고와는 의미가 다르다.    push: a number is inserted at the end of the queue.
대기열의 끝에 숫자를 삽입합니다.
    pop: the number from the front of the queue is taken out of the queue.
대기열의 시작 부분에서 숫자를 팝업합니다.
Can you rewrite the given expression such that the result of the algorithm using the queue is the same as the result of the original expression evaluated using the algorithm with the stack? 대기열 알고리즘을 사용한 결과가 이 창고 알고리즘을 사용한 원시 표현식 계산 결과와 같도록 다시 쓸 수 있습니까?
Input Specification
The first line of the input contains a number T (T ≤ 200).
첫 줄에 입력된 샘플 T 포함
The following T lines each contain one expression in postfix notation.
다음 T 접미사 입력
Arithmetic operators are represented by uppercase letters, numbers are represented by lowercase letters.
소문자는 조작수를 대표하고, 대문자는 조작부호를 대표한다.
You may assume that the length of each expression is less than 10000 characters.
표현식당 10000자를 초과하지 않음
Output Specification
For each given expression, print the expression with the equivalent result when using the algorithm with the queue instead of the stack.
주어진 표현식(접미사식)에 대해 출력은 창고 알고리즘 결과와 같고 대기열 알고리즘 결과의 표현식을 사용합니다.
To make the solution unique, you are not allowed to assume that the operators are associative or commutative.
해결 방안을 유일무이하게 하기 위해서, 조작부호가 관련되거나 교환된다고 가정해서는 안 된다.
Sample Input
이
xyPzwIM
abcABdefgCDEF
Sample Output
wzyxIPM
gfCecbDdAaEBF
제목: 번역에 아주 상세하게 썼다.
확인:
소문자를 만나면 바로 창고에 들어가고, 대문자 팝업 창고의 두 요소를 만나면왼쪽 포인터와 오른쪽 손가락을 두 요소로 가리켜 창고에 다시 넣습니다.
나무를 세운 후 두 갈래 나무의 층계를 두루 훑어보면 문제를 해결할 수 있다.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

struct Node{
	Node* left;
	Node* right;
	char ch;
};

const int N = 10010;

Node node[N]; // N 

Node* Q[N]; // 

void bfs(Node* root) {
	Q[0] = root; // 
	int front = 0;
	int rear = 1;
	while(front < rear) { // 

		Node* t = Q[front]->left;
		if(t != NULL) {
			Q[rear++] = t;
		}
		t = Q[front++]->right;
		if(t != NULL) {
			Q[rear++] = t;
		}
	}
	for(int i = rear-1; i >= 0; i--) {
		putchar(Q[i]->ch);
	}
	putchar('
');
}

int main() {
	int t;
	string str;
	int len;

	while(cin >> t) {
		while(t--) {
			cin >> str;
			stack<Node*> st;
			len = str.size();
			
			for(int i = 0; i < len ; i++) {
				
				node[i].ch = str[i];
				
				if( str[i] >= 'a' && str[i] <= 'z') { // 
					st.push(&node[i]);
					node[i].left = NULL;
					node[i].right = NULL;
				}
				else { // 
					node[i].right = st.top();
					st.pop();
					node[i].left = st.top();
					st.pop();
					st.push(&node[i]);
				}
			}
			Node* root = &node[len - 1];
			bfs(root); // 
		}
	}
	return 0;
}