Tree Traversals Again(PAT)

1.题目描述

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop().
Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

无序二叉树遍历可以使用堆栈以非递归方式实现。例如，假设当遍历一个6节点二叉树(键编号从1到6)时，堆栈操作是：Push(1)；Push(2)；Push(3)；POP()；POP()；Push(4)；POP()；POP(5)；Push(6)；POP()；POP()。然后，可以从这个操作序列生成唯一的二叉树(如图1所示)。您的任务是给出此树的后继遍历序列。

2.输入描述:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.
每个输入文件包含一个测试用例。对于每一种情况，第一行包含一个正整数N(<=30)，它是一棵树中的节点总数(因此节点编号从1到N)。接下来是2N行，每一行描述一个格式的堆栈操作：“Push X”，其中X是被推到堆栈上的节点的索引；或者“Pop”表示从堆栈中弹出一个节点。

3.输出描述:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
对于每个测试用例，在一行中打印对应树的后继遍历序列。一个解决方案是肯定存在的。所有的数字都必须用一个空格隔开，并且在行的末尾不能有额外的空格。

4.输入例子:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

5.输出例子:

3 4 2 6 5 1

6.源代码：

还没做出来-.-