The interview questions is to write a function Check:




bool Check(string input, List<Parenthesis> par)


Which would check input string and return true or false based on validation of parentheses inside the string. To be more clear, here are couple test cases:



string input="[()]{}()[]"; //Correct, assuming [](){} are delimiters



string input="[[)]"; //Incorrect, assuming same set of delimiters



Solution:



The key here is to realize that it can be simply done by using Stack. Alogorithm is to push open delimeters into the stack then we see then and pop them back then we see closing one. So, foreach char C of inout string S



1. If C is opening parenthes push it to the Stack and move to the next element



2. If C is closing parenthes and Stack is not empty pop element E from the stack:



            2a. if E is mached parenthes for C, continue to the next character in the string



            2b. if E is *not* mached parenthes for C, then string is incorrect.



2. If C is closing parenthes and Stack is empty, then string is incorrect.



3. If you reached end of string S and Stack is empty, then string is correct.

   
else string is incorrect.




Both computational and space complexity is O(n).




Here is sample solution in C#





public class Parenthesis
{
public char open;
public char close;
}





public static bool Check(string input, List<Parenthesis> par)
{
Stack<char> stack = new Stack<char>();

foreach (char letter in input)
{
bool isOpening = par.Exists(a => a.open == letter);
bool isClosing = par.Exists(a => a.close == letter);


if (isOpening)
stack.Push(letter);

if (isClosing)
{
if (stack.Count != 0)
{
char matchingLetter = stack.Pop();
bool match = par.Exists(a => (a.close == letter) && (a.open == matchingLetter));
if (!match)
return false;
}
else
return false;
}
}
return (stack.Count == 0);
}







Answers and Comments