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();
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( '>', '<' );
}
}
}