1673.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1673 on 2006-10-25 at 20:18:50 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int L_MAX = 8;
const int MAX = 51200;
 
class CartTree {
public:
	CartTree *left, *right, *parent;
	static CartTree *root;
	int priority;
	char label[L_MAX];
	bool operator <(const CartTree&) const;
	void make();
	void insert(CartTree*);
	void travel() const;
};
CartTree* CartTree::root = NULL;
bool CartTree::operator <(const CartTree& ct) const {
	return strcmp(label, ct.label) < 0;
}
void CartTree::make() {
	scanf("%*[' ']%[a-z]%*[/]%d", label, &priority);
	left = right = parent = NULL;
}
void CartTree::insert(CartTree *node) {
	if(priority > node->priority) {
		if(right != NULL) right->parent = node;
		node->left = right;
		right = node;
		node->parent = this;
	} else if(parent != NULL) parent->insert(node);
	else {
		node->left = this;
		parent = node;
		CartTree::root = node;
	}
}
void CartTree::travel() const {
	putchar('(');
	if(left != NULL) left->travel();
	printf("%s/%d", label, priority);
	if(right != NULL) right->travel();
	putchar(')');
}
 
int main() 
{
	CartTree node[MAX], *right;
	int n, i;
 
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) node[i].make();
		sort(node, node+n);
		right = NULL;
		for(i = 0; i < n; i++) {
			if(right == NULL) right = CartTree::root = &node[i];
			else {
				right->insert(&node[i]);
				right = &node[i];
			}
		}
		CartTree::root->travel();
		putchar('\n');
	}
	
	return 0;
}