// Given a nested list of integers, returns the sum of all integers in the
list
// weighted by their depth. For example, given the list {{1,1},2,{1,1}} the
// function should return 10 (four 1's at depth 2, one *2 at depth 1). Given
// the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one
4
// at depth 2, and *one 6 at depth 3)
int getNum(string::iterator &i, string::iterator end) {
if (i == end) {
return 0;
}
bool neg = false;
if (*i == '-') {
neg = true;
++i;
}
int res = 0;
while (i != end && isdigit(*i)) {
res = res * 10 + (*i - '0');
++i;
}
return neg ? -res : res;
}
int NestSum(string s) {
int multi = 0;
int res = 0;
for (auto i = s.begin(); i != s.end();) {
if (isdigit(*i) || *i == '-') {
res += getNum(i, s.end()) * multi;
} else {
if (*i == '{') {
++multi;
} else if (*i == '}') {
--multi;
}
++i;
}
}
return res;
}
class Nest {
struct Node {
int val;
bool isLeaf;
vector children;
Node (int n) : val(n), isLeaf(true) {}
Node () : isLeaf(false) {}
};
Node _root;
void CreateNode(string::iterator &left,
string::iterator right, Node *parent) {
while (left != right) {
if (isdigit(*left) || *left == '-') {
int num = getNum(left, right);
parent->children.push_back(Node(num));
} else {
if (*left == '{') {
++left;
Node res;
CreateNode(left, right, &res);
parent->children.push_back(res);
} else if (*left == '}') {
++left;
return;
} else {
++left;
}
}
}
}
void Print_(Node &n) {
if (n.isLeaf) {
cout << n.val << ',';
} else {
cout << '{';
for (auto child : n.children) {
Print_(child);
}
cout << "},";
}
}
int LevelSum(Node &cur, int level) {
int res = 0;
for (auto child : cur.children) {
if (child.isLeaf) {
res += child.val * level;
} else {
res += LevelSum(child, level + 1);
}
}
return res;
}
int LevelSumRevert(Node &cur, int *level) {
int tmp = 0;
int res = 0;
int maxLevel = 1;
for (auto child : cur.children) {
if (child.isLeaf) {
tmp += child.val;
} else {
int ll;
res += LevelSumRevert(child, &ll);
maxLevel = max(ll + 1, maxLevel);
}
}
*level = maxLevel;
return res + tmp * maxLevel;
}
public:
Nest(string s) {
auto left = s.begin() + 1;
auto right = s.end();
CreateNode(left, right, &_root);
}
void Print() {
Print_(_root);
cout << endl;
}
int LevelSum() {
return LevelSum(_root, 1);
}
int LevelSumRevert() {
int level;
return LevelSumRevert(_root, &level);
}
};
void NestSumTest() {
Nest nest("{{1,1},2,{1,1}}");
nest.Print(); cout << nest.LevelSum()
<< ' ' << nest.LevelSumRevert() << endl;
cout << NestSum("{3}") << ' ' << NestSum("{{1 }, 1,{1}}") << ' '
<< NestSum("{1,{4,{6}}}") << ' ' << NestSum("{{1,1},2,{1,1}}")
<< ' ' << NestSum("{-3}") << ' ' << NestSum("{{1,-1},-2,{1,1}}") <<
endl;
}
int main() {
NestSumTest();
WordsDistanceTest();
return 0;
}
