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();

Advertisements

One thought on “A Programming Job Interview Challenge #13 Follow up

  1. The same example, but mine goes through the whole string instead. Great Job. I am amazed we came to the same type of conclusion.


    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace Interperter
    {
    class Program
    {
    static Dictionary Language;

    static void Main(string[] args)
    {
    InitiailzeLanguage();

    string validString = "([]())";
    string inValidString = "({}";

    bool isValid = ValidateLanguage(validString);
    bool isInvalid = ValidateLanguage(inValidString);
    }

    private static bool ValidateLanguage(IEnumerable toValidate)
    {
    Stack characters = new Stack();

    foreach (char item in toValidate)
    {
    if (characters.Count > 0 && // make sure the stack is not empty
    Language.ContainsKey(item) && // make sure the character is the closing character
    characters.Peek() == Language[item]) // see if the opening tag is top most on stack
    characters.Pop(); // pop if we have success!
    else
    characters.Push(item); // didn't match, push on stack to try later
    }

    return characters.Count == 0;
    }

    private static void InitiailzeLanguage()
    {
    Language = new Dictionary();

    Language.Add( ')', '(');
    Language.Add( ']', '[');
    Language.Add( '}', '{');
    Language.Add( '>', '<' );
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s