Microsoft Interview Question
keep a counter for Parentheses, Bracket, and Curly.
let p = 0;
let b = 0;
let c = 0;
scanning from left to right on our sequence, if we see opening p or b or c, we increment by 1 the appropriate variable and decrement by 1 if we see a closing P or B or C.
From the above examples are not enough.
We check if the string is correct or not every time we see
1) A CLOSING sign. There are a few cases here.
2) an end of string character. p|c|b should all be zeros.
// psuedo code
bool Match(char token)
{
char c;
switch( c=ReadToken() )
{
case '{':
case '[':
case '(':
if(Match(c))
return Match(token);
return false;
case '}':
return (token=='{');
case ']':
return (token=='[');
case ')':
return (token=='(');
case END:
return false;
default:
return Match(token);
}
}
using a stack, if we see opening P, B or C, push, else if we see closing sign, do a pop, compare the two sign, if they are from same P, B or C, Correct.
- lvv May 20, 2007