forked from Dev-XYS/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cartesian-Tree.cpp
80 lines (72 loc) · 1.1 KB
/
Cartesian-Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NIL 0
using namespace std;
struct data
{
char id[100];
int pr;
}d[50010];
int n, lch[50010], rch[50010], S[50010], sp;
inline void parse(char *buf, char *str, int *num)
{
for (int i = 0; ; i++)
{
if (buf[i] == '/')
{
buf[i] = ' ';
break;
}
}
sscanf(buf, "%s %d", str, num);
}
void print_tree(int rt)
{
if (rt != 0)
{
printf("(");
print_tree(lch[rt]);
printf("%s/%d", d[rt].id, d[rt].pr);
print_tree(rch[rt]);
printf(")");
}
}
inline bool _data_cmp_(const data &x, const data &y)
{
return strcmp(x.id, y.id) < 0;
}
int main()
{
char temp[1000];
while (true)
{
scanf("%d", &n);
if (n == 0)
{
break;
}
for (int i = 1; i <= n; i++)
{
scanf("%s", temp);
parse(temp, d[i].id, &d[i].pr);
}
sort(d + 1, d + n + 1, _data_cmp_);
sp = 0;
for (int i = 1; i <= n; i++)
{
lch[i] = rch[i] = NIL;
S[sp] = 0;
while (sp > 0 && d[i].pr > d[S[sp - 1]].pr) sp--;
if (sp > 0)
{
rch[S[sp - 1]] = i;
}
lch[i] = S[sp];
S[sp++] = i;
}
print_tree(S[0]);
printf("\n");
}
return 0;
}