-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTree Grafting.cpp
53 lines (44 loc) · 1.24 KB
/
Tree Grafting.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
#include <iostream>
#include <string.h>
using std::string;
/*
Return the depth of the subtree rooted at the iterator position in the
input string and advance the iterator so that it ends up at the character
just beyond the ’u’ that ended the subtree traversal
*/
int depth(string::iterator& i) {
if (*i != NULL) {
int d {0}; // depth to find subtree end
string str {""};
do {
d += (*i=='d'?1:-1);
str += *i;
i++;
} while (*i != NULL && d != 0); // find subtree end
str = str.substr(1, str.size()-2); // new string of current subtree
string::iterator sub {str.begin()}; // new iterator current of subtree
d = depth(sub)+1; // depth of current subtree
int d2 {0};
if (*i != NULL) {
d2 = depth(i); // depth of next subtree
}
return (d>d2?d:d2);
} else {
return 0;
}
}
int main() {
string str = "dudduduudu";
string::iterator it;
it = str.begin();
std::cout << depth(it) << std::endl; // 2
str = "ddddduuuuu";
it = str.begin();
std::cout << depth(it) << std::endl; // 5
str = "dddduduuuu";
it = str.begin();
std::cout << depth(it) << std::endl; // 4
str = "dddduuduuu";
it = str.begin();
std::cout << depth(it) << std::endl; // 4
}