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: [[]]]][]][[][[[]
Content is available under GNU Free Documentation License 1.2.
