A Programming Job Interview Challenge #13 Follow up

Under repeated advisement of my work colleage he really wished to see me implement my psuedo code precisely. This made me realize there was one ambigiouity to my psuedo code was stack.Push should only be called if the character is NOT a matching close character. Now onto the code.

public void LanguageTest()
{
Hashtable language = new Hashtable();
language.Add(‘)’, ‘(‘);
language.Add(‘}’, ‘{‘);
language.Add(‘>’, ‘<‘);
language.Add(‘]’, ‘[‘);

bool valid = IsValidExpression(language, “([](<{}>))”);
valid = IsValidExpression(language, “({<)>}”);
}

private static bool IsValidExpression(IDictionary language, IEnumerable<char> expr)
{
Stack stack = new Stack();
foreach (char c in expr)
{
if (language.Contains(c))
{
if ((char) language[c] != (char) stack.Pop())
return false;
}
else
{
stack.Push(c);
}
}

return true;
}

BloggingContext.ApplicationInstance.CompleteRequest();

A Programming Job Interview Challenge #13

http://www.dev102.com/2008/07/21/a-programming-job-interview-challenge-13-brackets

Basically the question this is looking to solve is handling proper expression syntax/precedence similar to the standard calculator problem of solving 5+5/5=6 as opposed to solving it as 2.

Example of a legal expression: “([](<{}>))”.

Example of an illegal expression: “({<)>}”.

Which involes a much simpler version of Prefix or PostFix/Reverse Polish Notation ( http://en.wikipedia.org/wiki/Postfix_notation )  than the math expression since there are only pairs of operations. A rather basic psuedo code implementation of this could be done as follows

HashTable Close [ “)” -> “(“, “}” -> “{“, “>” -> “<“, “]” -> “[” ]; Stack holder;

Read expression

do while not end of expression {

if(close.ContainsKey(expression[i])) –Check to see if letter is a closing operand

{ –Reached closing operand, top of stack should be matching opening operand

if(close[expression[i] != stack.PopTop()) throw InvalidExpressionException

}

Push (expr[i])

} –Do looping to end of expression

BloggingContext.ApplicationInstance.CompleteRequest();