pku1785.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 115 行

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define SIZE 51000
using namespace std;

typedef struct Node
{
	char lab[8];
	int val;
};

int N;
Node V[SIZE];
int lc[SIZE], rc[SIZE];
char s[20];
int V_head;
int stack[SIZE];
int top;

bool cp_N(const Node &a, const Node &b)
{
	return a.val < b.val;
}

bool cp_S(const Node &a, const Node &b)
{
	return strcmp(a.lab, b.lab) < 0;
}

void Add(int i)
{
	char *p;
	p = s;
	while (*p != '/')
		p++;
	*p = 0;
	p++;
	strcpy(V[i].lab, s);
	V[i].val = atoi(p);
}

void Insert(int p)
{
	int i;
	int pos, q;
	pos = V_head;
	top = 0;
//	printf("head = %d\n", V_head);
	while (pos)
	{
		stack[top++] = pos;
//		printf("Finding %d\n", pos);
		pos = rc[pos];  //一直向右找到底
	}
//	printf("top = %d\n", top);
	while (top)
	{
		q = stack[top - 1];
		if (V[p].val < V[q].val)    //找到一个比要插入的点大的点
			break;
			top--;
	}
	if (top)
	{
		lc[p] = rc[q];
		rc[q] = p;
	}
	else
	{
		lc[p] = V_head;
		V_head = p;
	}
}

void Show(int p)
{
	printf("(");
	if (lc[p])
		Show(lc[p]);
	printf("%s/%d", V[p].lab, V[p].val);
	if (rc[p])
		Show(rc[p]);
	printf(")");
}

void Solve()
{
	int i;
	for (i = 1; i <= N; i++)
	{
		scanf("%s", s);
		Add(i);
	}
	sort(V + 1, V + N + 1, cp_S);
	memset(lc, 0, sizeof(lc));
	memset(rc, 0, sizeof(rc));
	V_head = 1;
	for (i = 2; i <= N; i++)
	{
		Insert(i);
//		Show(V_head);
//		printf("\n");
	}
	Show(V_head);
	printf("\n");
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
		Solve();
	return 0;
}