We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
The fourteenth post of the series of programming job interview challenge is out, 79 comments with answers were provided to job interview challenge #13. We didn’t publish a question last week due to a sever lack of time, so another week is gone and here we are again.
Mark R was the first to provide a correct and detailed answer (which I can quote here):
As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.
C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.
So, in one word, the most efficient answer is use a stack. Here is a nice image which was crafted by David Tchepak in his blog post Brackets, braces, parentheses, and other such creatures:
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd