Dev102's Challenge 13:Brackets

« Previous article:   Next article: »
Dev102's Challenge 12:Managed & unmanaged Blog Home Lists:Filter, Map and Reduce - and the Magic of IEnumerator.

Many people skipped last week’s challenge (like I had planned to). As it turned out, I was the only blogger to responded.

For this week’s challenge, they’ve gone back to a platform-neutral algorithm question:

Your input is a string which is composed from bracket characters. The allowed characters are:’(‘, ‘)’, ‘[’. ‘]’, ‘{‘, ‘}’, ‘<’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

The simple sentence answer is “use a stack, pushing on an open character, and popping on a close character”. There are a few other things to look out for, but that’s the basic concept. For the actual code, I bypassed any kind of library Stack class, since we wanted the most efficient and for the very limited needs of this function, I could jury-rig a faster one out of a char array. Complexity is speed: O(N), space O(N)

comments powered by Disqus