fbpx

C++: Flatten a List

Bjarne-stroustrup
 

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]

SOURCE

Content is available under GNU Free Documentation License 1.2.