Write a function to flatten the nesting in an arbitrary list of values. Your program should work on the equivalent of this list:
[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]
Where the correct result would be the list:
[1, 2, 3, 4, 5, 6, 7, 8]
#include <list> #include <boost/any.hpp> typedef std::list<boost::any> anylist; void flatten(std::list<boost::any>& list) { typedef anylist::iterator iterator; iterator current = list.begin(); while (current != list.end()) { if (current->type() == typeid(anylist)) { iterator next = current; ++next; list.splice(next, boost::any_cast<anylist&>(*current)); current = list.erase(current); } else ++current; } }
Use example:
Since C++ currently doesn’t have nice syntax for initializing lists, this includes a simple parser to create lists of integers and sublists. Also, there’s no standard way to output this type of list, so some output code is added as well.
#include <cctype> #include <iostream> // ******************* // * the list parser * // ******************* void skipwhite(char const** s) { while (**s && std::isspace((unsigned char)**s)) { ++*s; } } anylist create_anylist_i(char const** s) { anylist result; skipwhite(s); if (**s != '[') throw "Not a list"; ++*s; while (true) { skipwhite(s); if (!**s) throw "Error"; else if (**s == ']') { ++*s; return result; } else if (**s == '[') result.push_back(create_anylist_i(s)); else if (std::isdigit((unsigned char)**s)) { int i = 0; while (std::isdigit((unsigned char)**s)) { i = 10*i + (**s - '0'); ++*s; } result.push_back(i); } else throw "Error"; skipwhite(s); if (**s != ',' && **s != ']') throw "Error"; if (**s == ',') ++*s; } } anylist create_anylist(char const* i) { return create_anylist_i(&i); } // ************************* // * printing nested lists * // ************************* void print_list(anylist const& list); void print_item(boost::any const& a) { if (a.type() == typeid(int)) std::cout << boost::any_cast<int>(a); else if (a.type() == typeid(anylist)) print_list(boost::any_cast<anylist const&>(a)); else std::cout << "???"; } void print_list(anylist const& list) { std::cout << '['; anylist::const_iterator iter = list.begin(); while (iter != list.end()) { print_item(*iter); ++iter; if (iter != list.end()) std::cout << ", "; } std::cout << ']'; } // *************************** // * The actual test program * // *************************** int main() { anylist list = create_anylist("[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]"); print_list(list); std::cout << "\n"; flatten(list); print_list(list); std::cout << "\n"; }
- Output:
[[1], 2, [[3, 4], 5], [[[]]], [[[6]]], 7, 8, []] [1, 2, 3, 4, 5, 6, 7, 8]
Content is available under GNU Free Documentation License 1.2.