?? pku1785.cpp
字號(hào):
#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) //找到一個(gè)比要插入的點(diǎn)大的點(diǎn)
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;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -