fbpx

C++: Balanced Brackets

Bjarne-stroustrup
 

Task:

  • Generate a string with N opening brackets (“[”) and N closing brackets (“]”), in some arbitrary order.
  • Determine whether the generated string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.

Examples:

   (empty)   OK
   []        OK   ][        NOT OK
   [][]      OK   ][][      NOT OK
   [[][]]    OK   []][[]    NOT OK

#include <algorithm>
#include <iostream>
#include <string>

std::string generate(int n, char left = '[', char right = ']')
{
	std::string str(std::string(n, left) + std::string(n, right));
	std::random_shuffle(str.begin(), str.end());
	return str;
}

bool balanced(const std::string &str, char left = '[', char right = ']')
{
	int count = 0;
	for (std::string::const_iterator it = str.begin(); it != str.end(); ++it)
	{
		if (*it == left)
		count++;
		else if (*it == right)
		if (--count < 0) return false;
	}
	return count == 0;
}

int main()
{
	srand(time(NULL)); // seed rng
	for (int i = 0; i < 9; ++i)
	{
		std::string s(generate(i));
		std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n";
	}
}

Output:

 ok: 
 ok: []
 ok: [][]
bad: []][[]
 ok: [[[]][]]
bad: ][[[[]][]]
 ok: [[[]][[]][]]
bad: ]][[]][[[[][]]
bad: [[]]]][]][[][[[]

SOURCE

Content is available under GNU Free Documentation License 1.2.