Last active
August 29, 2015 14:02
-
-
Save mceckstein/120bbef24e34c6f06d67 to your computer and use it in GitHub Desktop.
Balanced Delimiters problem (C# iterative solution)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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