Skip to content

Instantly share code, notes, and snippets.

@mceckstein
Last active August 29, 2015 14:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mceckstein/120bbef24e34c6f06d67 to your computer and use it in GitHub Desktop.
Save mceckstein/120bbef24e34c6f06d67 to your computer and use it in GitHub Desktop.
Balanced Delimiters problem (C# iterative solution)
using System;
using System.Collections.Generic;
using System.Linq;
public class BalancedDelimiters
{
/// <summary>
/// Dictionary that maps the delimiter characters that the
/// input text may contain. The key represents the opening delimiter,
/// the value represents the key's corresponding closing delimiter.
/// </summary>
private static readonly Dictionary<char, char> groupChars = new Dictionary<char, char>()
{
{ '(', ')' },
{ '{', '}' },
{ '[', ']' }
};
static void Main(string[] args)
{
// get the input from the user
string s = Console.ReadLine();
// a stack suits this exercise, since it matches
// the semantics of nested delimiters. we could also
// do this recursively, but a stack feels cleaner.
Stack<char> stack = new Stack<char>();
// let's iterate over each character
foreach (char c in s.ToCharArray())
{
if (IsOpening(c))
{
// if it's an opening character we can always insert it
stack.Push(c);
}
else if (stack.Any() && IsClosingGroup(stack.Peek(), c))
{
// if it's a closing character for the character at the top
// of the stack, then we can take off that character from the stack
stack.Pop();
}
else
{
// otherwise, push it
stack.Push(c);
}
}
// if, after this exercise there are any more characters
// on the stack, we know that we have failed
if (stack.Count > 0)
{
Console.WriteLine("False");
}
else
{
Console.WriteLine("True");
}
}
/// <summary>
/// Return true if the character represents an 'opening'
/// delimiter
/// </summary>
static bool IsOpening(char c)
{
return groupChars.ContainsKey(c);
}
/// <summary>
/// Return true if the current delimiter closes the
/// last-seen delimiter
/// </summary>
static bool IsClosingGroup(char previous, char current)
{
return groupChars.ContainsKey(previous) && groupChars[previous] == current;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment