The thirteen post of the series of programming job interview challenge is out, Only 13 comments with answers were provided to job interview challenge #12. This is a small amount comparing to the previous challenges, but I realize and understand that it was language specific and not very trivial challenge…
Jason Kikel was the first one to solve the question, and here is his short answer:
UnmanagedClass is referencing an address on ManagedClass without pinning it. The ManagedClass instance needs to be pinned so the GC won’t move it to another location during a collection.
In other words, I didn’t use the _pin keyword when I allocated the managed class. The process of pinning a managed object, cause the Common Language Runtime (CLR) Garbage Collector (GC) not to relocate and move the object in memory. So, when we pass managed data to unmanaged code, pinning is necessary.
James Curran posted the solution in his blog - http://honestillusion.com/blogs/blog_0/archive/2008/07/16/dev102-s-challenge-12-managed-unmanaged.aspx.
Those are the other readers who provided a correct solution for last week challenge: befarino, leppie, Christof Jans and Jelle Hissink.
This Week Question:
Your input is a string which is composed from bracket characters. The allowed characters are:’(', ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.
Example of a legal expression: “([](<{}>))”.
Example of an illegal expression: “({<)>}”.
Provide the most efficient, elegant and simple solution for that problem.I think that this is a well known problem but I am not sure, so excuse me if this week’s question is screwed.
Get updates by RSS to catch up with the next posts in this series and to get the correct answer for today’s question. As always you may post the solution in your blog or comment. Comments with answers will be approved only next week.
By sirrocco on Jul 21, 2008 | Reply
Use a stack.
if (is open bracket)
push(bracket)
else if (is closing bracket) and (in the stack)
pop(bracket)
else if (is closing bracket) and (not in the stack)
message not valid
By Omar on Jul 21, 2008 | Reply
I would use a stack, and expect the following to return true for valid input:
initialise stack
for each character c in input
{
if (isOpeningBrace(c))
{
stack.push(c)
}
else
{
bracket = stack.pop()
if (bracket != c) return false
}
}
// check that every opening bracket was closed
if (stack.size() != 0) return false
return true;
By Jason Kikel on Jul 21, 2008 | Reply
Use a stack. Read each character of the input string and if its a left bracket /[\(\{\[’ matches ‘ 0 after the input string is fully read return invalid otherwise return valid.
By Mark R on Jul 21, 2008 | Reply
As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.
C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.
By Mark R on Jul 21, 2008 | Reply
Ah, I forgot about the recursive solution.
Create a function which takes a pointer or index into a string as an input/output parameter and returns true/false. If the string is empty, return true; otherwise examine the first character and return false if it is not an opening bracket. Advance the pointer and call the funtion recursively; if it returns false, return false as well. Otherwise check the next character from the input, if it’s the matching closing bracket advance the pointer and return true, otherwise return false.
By Trinity on Jul 21, 2008 | Reply
Here is my O(n) solution.
You can use a stack to determine if the given input string is valid or not.
1) Start at the beginning of the string and read it character by character.
2) If the current character is an open bracket i.e. any one of (, [, {, then pop the element (head) of the stack and compare it with the current character. If they are of the same type, move to the next character. Else print error message saying that the string is not valid and exit.
4) Do steps 2 and 3 till the end of the string. 5) If there are no more characters to process then print the input string is valid.
By James Curran on Jul 21, 2008 | Reply
My solution is posted here:
http://honestillusion.com/blogs/blog_0/archive/2008/07/21/dev102-s-challenge-13-brackets.aspx
(So, am I the first with full code?)
By Justin Etheredge on Jul 21, 2008 | Reply
Here is a quick C# solution:
string parens = “()[]{}”;
Stack stack = new Stack();
foreach (char c in value)
{
int index = parens.IndexOf(c);
if ((index % 2) == 0)
{
stack.Push(c);
}
else
{
if (stack.Count 0) return false;
return true;
By Michael Mrozek on Jul 21, 2008 | Reply
Read the string from left to right. Push each opening symbol onto a stack. When a closing symbol is encountered, pop the stack and make sure the top of stack was the matching opening symbol. If it isn’t, or if the string is empty and the stack isn’t, the string is bad; otherwise, it’s good
By Nate on Jul 21, 2008 | Reply
How about this…
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Validator.Validate(”([]())”));
Console.WriteLine(Validator.Validate(”({}”));
Console.WriteLine(Validator.Validate(”abc”));
Console.ReadKey();
}
}
static class Validator
{
static readonly List Starts = new List { ‘(’, ‘[', '{', '<' };
static readonly List Ends = new List { ')', ']‘, ‘}’, ‘>’ };
private static readonly Dictionary Pairs = new Dictionary { { ‘(’, ‘)’ }, { ” }, { ‘[', ']‘ }, { ‘{’, ‘}’ }, { ‘)’, ‘(’ }, { ‘>’, ‘<’ }, { ‘]’, ‘[' }, { '}', '{' } };
internal static string Validate(string input)
{
Stack current = new Stack();
int index = -1;
foreach (char value in input)
{
index++;
if (Starts.Contains(value))
{
current.Push(value);
}
else if (Ends.Contains(value))
{
if (current.Peek() != Pairs[value])
{
return GetMessage(”Out-of-Sequence character”, value, index);
}
else
{
current.Pop();
}
}
else
{
return GetMessage(”Illegal character”, value, index);
}
}
return “Valid”;
}
private static string GetMessage(string message, char character, int charNumber)
{
return string.Format(”{0} - {1} - index {2}”, message, character, charNumber);
}
}
}
By Kevin Hjelden on Jul 21, 2008 | Reply
Simply keep a stack of the open characters, and only allow a closing of the most recent one:
string opens = “[{)”;
bool validate(string s)
{
vector stack;
foreach (char c in string)
{
if (c in opens)
{
// push on to stack when open character received
stack.push(opens.position(c));
}
else if (c in closes)
{
// make sure it’s a valid closing
int last = stack.pop();
if (last != closes.position(c))
return false;
}
else
{
// must be an opening or closing
return false;
}
}
return true;
}
By Jeremy Weiskotten on Jul 21, 2008 | Reply
A simple stack would work. Iterate over each character in the string. If you have an open bracket, push it onto the stack. If you have a close bracket, pop the last start bracket you added off the stack and test for a match with your close bracket.
By hi on Jul 21, 2008 | Reply
http://www.java2s.com/Code/Java/Collections-Data-Structure/BracketChecker.htm
By Alex on Jul 21, 2008 | Reply
A recursive method would work best, which works as follows:
Based on the first char in the string, find the index of the matching closing character.
Example will be using: ({([][])}{}())[]
Do this by counting- +1 for each instance of that opening character, -1 for each corresponding closing character, starting with the opening character. So ({([][])}{}())[] would be +1,+1,-1,+1,-1,-1. We’re at Zero, so that last ) is the one we want. If you get to the end of the string and never make it to 0, the whole thing is invalid. Return false.
Otherwise, take the substring between the opening char (first char in this string) and closing char (whose index you just determined), and recursively call this function on that substring- in this example, it would be “{([][])}{}()”. If that returns false, return false. Otherwise, move on to the next substring peice: in this case, “[]“. Check every enclosed substring recursively this way, and if any of them return false, return false. If you make it to the end of the string and don’t have anything open-ended, and none of your recursively checked substrings returned false, than congrats! You’re valid. Return true.
By S Javeed on Jul 21, 2008 | Reply
Perl Solution. Run as follows:
echo “({}” | perl ./brackets.pl
echo “([]())” | perl ./brackets.pl
or just run brackets.pl and enter the various strings followed by a newline after each string.
Code:
#!/usr/bin/perl
sub checkBrackets ($) {
my ($input) = @_;
chomp $input;
my $bracketType = {
“(” => 0.1,
“)” => 0.2,
“[" => 1.1,
"]” => 1.2,
“{” => 2.1,
“}” => 2.2,
” 3.1,
“>” => 3.2,
};
my $status = 1;
my $i = 0;
my @stack = ();
my $chr;
for ($i = 0; $i {$chr});
if ($type =~ /\.1$/) {
push @stack, $chr;
} elsif ($type =~ /\.2$/) {
if (int($bracketType->{$chr}) == int($bracketType->{$stack[-1]})) {
pop @stack;
} else {
last;
}
}
}
$status = 0 if (@stack);
return $status;
}
while (my $line = ) {
chomp $line;
my $result = checkBrackets($line);
print “$line: ” . ($result ? “LEGAL” : “ILLEGAL”) . “\n”;
}
By Steven Baker on Jul 21, 2008 | Reply
easily done with a stack
By leppie on Jul 22, 2008 | Reply
I think this question is to tempt a Regex answer, but that will be wrong (and impossible!).
The answer is simply using a stack, then moving left to write, pushing opening ‘parenthesis’ and and asserting when popping a closing ‘parenthesis’. Any assert fail, deems the sequence invalid.
By Morgan Cheng on Jul 22, 2008 | Reply
Solution: Iterate the string and track left brackets with a stack.
Create a stack to hold all open left brackets. “Open” means we haven’t found its matching right brackets yet. For each char in the string (from left to right), if the stack is empty, we push current char into the stack only if it is a left bracket char, otherwise its a invalid string for sure; if the stack is not empty, we check whether current char is a left bracket or right bracket. For left bracket, we just push it to stack; for right bracket, we compare it with the top char in char. If they are matching brackets, we continue, otherwise it is a invalid string.
After the string is iterated, if the stack is empty, it is valid string; otherwise it is invalid.
Both time complexity and space complexity are O(n), since it traverse the whole string and need a O(n) stack. Below is a C#3 implementation.
static Dictionary bracketPairs = new Dictionary()
{
{ ‘)’, ‘(’ },
{ ‘]’, ‘[' },
{ '>', '<' },
{ '}', '{' },
};
static HashSet m_leftBrackets = new HashSet() { '(', '[', '<', '{' };
static HashSet m_rightBrackets = new HashSet() { ')', ']‘, ‘>’, ‘}’ };
public static bool IsValidString(string str)
{
Stack bracketStack = new Stack();
foreach (char ch in str)
{
if (bracketStack.Count == 0)
{
if (m_leftBrackets.Contains(ch))
{
bracketStack.Push(ch);
}
else
{
return false;
}
}
else
{
if (m_leftBrackets.Contains(ch))
{
bracketStack.Push(ch);
}
else if (m_rightBrackets.Contains(ch))
{
char topChar = bracketStack.Pop();
if (topChar != bracketPairs[ch])
{
return false;
}
}
else
{
return false; // has invalid char
}
}
}
return (bracketStack.Count == 0);
}
By Hello world on Jul 22, 2008 | Reply
#include
#include
static const unsigned char close_match[256] = {
['('] ‘)’,
['{'] ‘}’,
['',
['['] ‘]’,
};
static int
match(const unsigned char *s)
{
unsigned char stack[strlen(s)];
int sp = 0;
for (; *s; s++) {
if (close_match[*s]) {
stack[sp++] = close_match[*s];
} else if (sp == 0 || *s != stack[--sp]) {
return 0;
}
}
return sp == 0;
}
int
main(int ac, char **av)
{
if (ac != 2) {
printf(”Usage: %s string\n”, av[0]);
return -1;
}
printf(”%slegal\n”, match((const unsigned char *) av[1]) ? “” : “il”);
return 0;
}
By Liming Zhang on Jul 22, 2008 | Reply
If one such expression is legal, it must contain at least on pair of bracket–one of leftward, one of righward, with no any other character between them.
So, my solution:
Search the whole string to find such a pair of bracket metioned above. If found, remove them, and search again.
Condition of legal string: after times of removal, this string must become a string with length of zero.
By herval on Jul 22, 2008 | Reply
my quick and dirty solution:
make a set of stacks, one for each character pair - pushing when it’s an open (, { or .
- raise error when popping from an empty stack
- raise an error at the end of the string, if any stack is still full
By Samuel Williams on Jul 22, 2008 | Reply
This should work! Hopefully ^_^
#!/usr/bin/env ruby
L = {”(” => “)”, “[" => "]“, “{” => “}”, ” “>”}
good = “([]())”
bad = “({}”
# Performance is O(N) with memory requirement O(N/2)
def check(input)
# Stack to record what to expect next
s = []
input.split(//).each do |c|
puts “#{c}: #{s.inspect}”
if L.key? c
s << L[c]
else
d = s.pop
if d != c
puts “Error got #{c} but expecting #{d}”
return
end
end
end
end
puts “Checking good…”
check(good)
puts “Checking bad…”
check(bad)
By dextar on Jul 22, 2008 | Reply
My attempt in Python (was a fun way to try some python :-))
def valid_str(str):
stack = []
brackets = { ”, ‘(’ : ‘)’, ‘{’ : ‘}’, ‘[' : ']‘ }
for c in str:
closer = brackets.get(c)
if closer != None:
stack.append(closer)
elif len(stack) == 0 or c != stack.pop():
return False
return len(stack) == 0
By dextar on Jul 22, 2008 | Reply
Oops! Don’t know how to write code in the comments.
# brackets should also contain a less than and greater than pair, but it gets stripped as HTML tags I guess.
# also, the indenting dissapears (which is very important in python.
trying with a ‘pre’ below. If not, well, you know what I meant
def valid_str(str):
stack = []
brackets = { ”, ‘(’ : ‘)’, ‘{’ : ‘}’, ‘[' : ']‘ }
for c in str:
closer = brackets.get(c)
if closer != None:
stack.append(closer)
elif len(stack) == 0 or c != stack.pop():
return False
return len(stack) == 0
By macmariman on Jul 22, 2008 | Reply
Create a stack, iterate the input string, push char if it is any opening bracket. If it is closing bracket then compare with the top of the stack, if they are the ’same kind’ (current char is closing bracket for the top of the stack) pop it and continue iteration else return false. At the end if the stack is empty return true else return false.
By Haskell programmer on Jul 22, 2008 | Reply
module Main () where
main = do s <- getLine
putStrLn $ match s []
leftToRight c = case c of
‘ ‘>’
‘{’ -> ‘}’
‘[' -> ']‘
‘(’ -> ‘)’
otherwise -> ‘x’
match (a:b) (c:d) | a == c = match b d
match (a:b) c = match b ((leftToRight a):c)
match [] [] = “legal”
match _ _ = “illegal”
By Darrell Wright on Jul 22, 2008 | Reply
This is just a matter of pushing popping peeking a stack. Just push a valid left bracket and when a right bracket is encountered, peek at the top of the stack and see if it is the matching left bracket. If it isn’t, the string is invalid. If you finish and haven’t encountered an invalid, it is valid. Not many other ways to do this efficiently.
public static bool checkBrackets( string testString ) {
List leftBrackets = new List( ) { ‘(’, ‘[', '{', '<' };
List rightBrackets = new List( ) { ')', ']‘, ‘}’, ‘>’ };
Stack stk = new Stack( );
int pos;
for( int n = 0; n = 0 ) {
stk.Push( testString[n] );
} else if( (pos = rightBrackets.IndexOf( testString[n] )) >= 0 ) {
if( stk.Peek( ) != leftBrackets[pos] ) {
return false;
} else {
stk.Pop( );
}
}
}
return true;
}
By Ryan on Jul 22, 2008 | Reply
This is simply a LIFO stack. When you encounter a closing bracket, pop the last opening brace off the stack, if it’s not the corresponding opening bracket, then the input is illegal.
By Shams Mahmood on Jul 22, 2008 | Reply
This method works by looping through each of the characters and maintaining a stack of unmatched opening brackets. Whenever an opening bracket is found it is pushed into the stack, when a closing bracket is found the stack head is checked for the corresponding opening bracket. If such a bracket is found then the stack head is ‘popped’ else we report an error. At the end of this loop if the stack is empty then the expression is valid.
Time complexity: O(n) [Each character is being processed with constant time to push, pop and peek the stack]
Space complexity: O(n) [Maximum of n characters can be inside the stack at a time]
public static boolean isExpressionValid(final String pInput) {
Stack eOpeningBraces = new Stack();
for( int i = 0; i < pInput.length(); i++ ) {
char eLoopChar = pInput.charAt(i);
if( isOpeningBrace(eLoopChar) ) {
eOpeningBraces.push(eLoopChar);
} else if( isClosingBrace(eLoopChar) ) {
if( eOpeningBraces.isEmpty() ) {
return false;
}
char eHeadOfStackChar = eOpeningBraces.peek();
if( isOpenCloseMatching(eHeadOfStackChar, eLoopChar) ) {
eOpeningBraces.pop();
} else {
return false;
}
}
}
return eOpeningBraces.isEmpty();
}
public static boolean isOpeningBrace(final char pInput) {
return (
(pInput == ”) ||
(pInput == ‘)’) ||
(pInput == ‘]’) ||
(pInput == ‘}’)
);
}
public static boolean isOpenCloseMatching(final char pOpen, final char pClose) {
return (
(pOpen == ”) ||
(pOpen == ‘(’ && pClose == ‘)’) ||
(pOpen == ‘[' && pClose == ']‘) ||
(pOpen == ‘{’ && pClose == ‘}’)
);
}
By Kimmen on Jul 22, 2008 | Reply
By using a hash table and a stack you will be able to verify the input. The hash table contains a map between the start bracket character and it’s corresponding end bracket. The stack holds all the end bracket characters that has to be matched.
For each character, let’s call it a token, in the input string check if it’s a start bracket. If it is, put it’s corresponding end bracket in the stack. But if it’s not a start bracket, check with the top of the stack if the token is the end bracket we are looking for. If it is, pop if from the stack and continue. If the token is neither a start bracket nor the end bracket we are looking for, the input is invalid. After checking each token, the input string is valid if the stack is empty =).
Here’s the code:
private static IDictionary tTable = new Dictionary
{
{’(',’)'},
{’[',']‘},
{”},
{’{',’}'},
};
private static bool ParseBracketString
(string input)
{
var tokens = new Stack(input.Length);
foreach (var token in input)
{
if (tTable.ContainsKey(token))
{
tokens.Push(tTable[token]);
}
else if (tokens.Peek().Equals(token))
{
tokens.Pop();
}
else
{
return false;
}
}
return tokens.Count == 0;
}
By Terje Myklebust on Jul 22, 2008 | Reply
This is my solution:
private static bool ValidateBrackets(IEnumerable inputString)
{
// I put all the allowed “bracket sets” into a dictionary.
// This simplifies (shortens) the code, but is probably a bit
// slower than doing direct comparision for each of our allowed characters
// The closing bracket is put in as the key, because we only need to find our
// opening bracket based on the closing bracket, not the other way around.
var allowedBrackets = new Dictionary(4);
allowedBrackets.Add(’}', ‘{’);
allowedBrackets.Add(’)', ‘(’);
allowedBrackets.Add(’]', ‘[');
allowedBrackets.Add('>', '<');
// We add a stack where we will store all our currently
// (as we iterate the string) opened brackets
var openBrackets = new Stack(8);
foreach (Char c in inputString)
{
// First we check if the current char is a opening bracket, and if it is,
// we add it to our stack. If not, we check if it is a closing bracket
// and follow up with a check to see that it is closing the last opened bracket
// by looking up the value (opening bracket) in allowedBrackets using the key (closing bracket)
if(allowedBrackets.ContainsValue(c))
openBrackets.Push(c);
else if(allowedBrackets.ContainsKey(c))
{
if(openBrackets.Pop() != allowedBrackets[c])
return false;
}
}
return openBrackets.Count == 0;
}
By Jelle Hissink on Jul 22, 2008 | Reply
You could just walk through the string, and maintain a list of currently open brackets (FILO list). It could look like: (from my head, so it might not compile
public bool CheckBrackets(string input) {
Stack openBrackets = new Stack();
foreach (char c in input) {
char? expectedOpenBracket = null;
switch (c) {
case ‘{’:
case ‘[’:
case ‘(’:
case ”:
expectedOpenBracket = ‘<’;
break;
}
if (expectedOpenBracket.HasValue) {
if (openBrackets.Count == 0) {
return false; // no open bracket, so no match
}
if (openBrackets.Pop() != expectedOpenBracket.Value) {
return false; // no match
}
}
}
return openBrackets.Count == 0; // we should have closed all brackets by now…
}
By Matt Howells on Jul 22, 2008 | Reply
Create a char stack.
Iterate through each char in the string.
If char is an opening, push it onto the stack.
If char is a closing, pop a char off the stack and make sure they match (e.g. ‘{’ and ‘}’)
If they do not match or the stack was empty then the string is invalid.
By returning the index of the char you have got to you could indicate to where the string is wrong.
By Dave Amphlett on Jul 22, 2008 | Reply
Here’s my first comment on these challenges. Nothing amazing just a pretty straight forward solution:
public class ValidatingBracketStack
{
public static bool Validate(string input)
{
ValidatingBracketStack stack = new ValidatingBracketStack();
foreach (char c in input.ToCharArray())
if (!stack.Next(c))
return false;
return stack.IsEmpty;
}
private Stack _stack = new Stack();
public bool Next(char c)
{
switch (c)
{
case ‘{’:
case ‘(’:
case ‘[’:
case ”:
return PopAndMatchAgainst(’<’);
default:
return false;
}
}
public bool IsEmpty
{
get { return _stack.Count == 0; }
}
private bool PopAndMatchAgainst(char c)
{
return (IsEmpty) ? false : (_stack.Pop() == c);
}
}
By levi on Jul 22, 2008 | Reply
This is in Java: http://docs.google.com/View?docID=dppnxf9_3zhpzzrgv
By levi_h on Jul 22, 2008 | Reply
I’m not sure whether my previous comment was added or not (it doesn’t seem that way), but I’ve written a solution in Java: http://docs.google.com/View?docID=dppnxf9_3zhpzzrgv
By Mark Brackett on Jul 22, 2008 | Reply
Iterate the char array, adding open tokens to a stack. When you hit a close token, verify that it matches the popped open tag.
C#:
// Note they’re in the same order
const string OPEN = “([{”.ToCharArray();
Stack openTokens = new Stack();
foreach(char c in s.ToCharArray()) {
if (int i = OPEN.IndexOf(c) >= 0) {
// open token
openTokens.Push(i);
} else {
// close or invalid token
if (CLOSE[openTokens.Pop()) != c) {
throw new InvalidFormatException();
}
}
}
By configurator on Jul 22, 2008 | Reply
private static readonly Dictionary legalBrackets = new Dictionary { {’(', ‘)’},
{’[', ']‘},
{’{', ‘}’},
{”}};
private static bool Legal(string brackets) {
Stack stack = new Stack();
foreach (char c in brackets) {
char closer;
if (legalBrackets.TryGetValue(c, out closer))
stack.Push(closer);
else if (stack.Pop() != c)
return false;
}
return stack.Count == 0;
}
———————————————–
Basically, we create a dictionary where the starting brackets points to the ending one.
For each character, if the character is a starting bracket, we push the corresponding ending bracket to a stack. For every character that is not a starting bracket, the character must be the first character in the stack, so we Pop and compare.
This code does not allow any character other than brackets; to allow, we would need to change the line
if (stack.Pop() != c)
to
if (legalBrackets.ContainsValue(c) && stack.Pop() != c)
By Tim Kington on Jul 22, 2008 | Reply
boolean isValid(String str)
{
Stack stack = new Stack();
for(int i = 0; i < str.length(); i++)
{
char c = str.charAt(i);
switch(c)
{
case ‘(’:
case ‘{’:
case ‘[’:
case ”:
if(c != stack.pop())
return false;
break;
}
}
}
This should really also catch StackEmptyException and return false there, too.
By valera on Jul 22, 2008 | Reply
Obvious solution:
Some sort of finite-state machine,
Complicity: o(n)
Memory: not more than o(n)
Algorithm (pseudo code):
foreach(char C in inputString)
{
if(C is openingBracket) stack.push(C)
else if(stack.pop() is not same bracket as C)
return false;
}
return true;
BTW Stack structure can be replaced with bit array of 2bit structures (to encode 4 types of brackets)
By Christof Jans on Jul 22, 2008 | Reply
static bool IsValid(string inputString)
{
Stack stack = new Stack();
foreach (char c in inputString)
{
switch (c)
{
case ‘(’:
case ‘{’:
case ‘[':
case ' 0 && stack.Peek() == '(') stack.Pop();
else return false;
break;
case '}':
if (stack.Count > 0 && stack.Peek() == '{') stack.Pop();
else return false;
break;
case ']‘:
if (stack.Count > 0 && stack.Peek() == ‘[’) stack.Pop();
else return false;
break;
case ‘>’:
if (stack.Count > 0 && stack.Peek() == ‘<’) stack.Pop();
else return false;
break;
}
}
return stack.Count == 0;
}
By Mike G. on Jul 22, 2008 | Reply
Well, I don’t know if this is efficient, elegant, OR simple, but it is short
In any language, I believe that the solution lies in eliminating matched “inner” pairs until either all the brackets have been eliminated, or something unmatched is found.
This script does it by using perl substitutions to repeatedly remove the pairs. Success happens if the string is empty after all the removals possible are done.
perl -ne’chomp; my $line=$_; while(s/\(\)//g||s///g||s/\[\]//g||s/\{\}//g){};if(length){print “$line is INVALID\n”;}else {print “$line is VALID\n”}’
By Michael on Jul 22, 2008 | Reply
Nice question, but very academical :).
Stack is best structure for controlling nested elements.
Algorithm is simple. If we found ‘open’ bracket push them to stack, if we found ‘close’ bracket and stack is empty or top of stack not equal arbitrary ‘open’ bracket for found ‘close’ bracket then we illegial string, otherwise we pop top element from the stack
At the end if stack is empty then we have correct string without any nesting problem with brackets.
Here is program:
using System;
using System.Collections.Generic;
public class MyClass {
static string openBrackets = @”{[)";
private static bool checkBrackets(string testString) {
Stack brackets = new Stack();
foreach (char c in testString) {
if (openBrackets.IndexOf(c) != -1) {
brackets.Push(c);
} else {
int pos = closeBrackets.IndexOf(c);
if ( pos != -1) {
if ((brackets.Count == 0) || (brackets.Peek() != openBrackets[pos]) ) {
return false;
} else {
brackets.Pop();
}
}
}
}
return (brackets.Count == 0);
}
public static void Main() {
Console.WriteLine(String.Format(”String {0}: result: {1}”, @”{aaaaaaaa}”, checkBrackets(@”{aaaaaaaa}”)));
Console.WriteLine(String.Format(”String {0}: result: {1}”, @”([]())”, checkBrackets(@”([]())”)));
Console.WriteLine(String.Format(”String {0}: result: {1}”, @”({}”, checkBrackets(@”({}”)));
Console.WriteLine(String.Format(”String {0}: result: {1}”, @”{aaaaaaa}”, checkBrackets(@”{aaaaaaa}”)));
Console.WriteLine(String.Format(”String {0}: result: {1}”, @”(a”, checkBrackets(@”(a”)));
}
}
By Mike G. on Jul 22, 2008 | Reply
Ooops, after a bit of thought, this can be a lot shorter and clearer.
perl -ne’1 while(s/\(\)||\[\]|\{\}//g);print “NOT ” if length>1;print”OK\n”‘
Basically, remove all inner matching characters from the string, and repeat until you can’t.
By Charles on Jul 22, 2008 | Reply
Recursivly use a regex to find the groups with a pattern such as
([\(][\)])|([\[][\]])|([\{][\}])|([\])
Check for a remainder when no matches are found. A remainder would indicate an invalid match
By Mike G. on Jul 22, 2008 | Reply
Note that for long strings, the O(n^2) nature of the s/// solution starts to bite. In that case, it’s better to code up something that keeps the seen string in memory and just deletes off the last character if it’s an opening character and it’s matching close is read. Otherwise, append the read character to the string.
By Jon von Gillern on Jul 22, 2008 | Reply
Thanks!
http://www.vonsharp.net/ProgrammingJobInterviewChallenge13Answer.aspx
By Richard Vasquez on Jul 22, 2008 | Reply
Just off the top of my head without thinking (and I’m sure there will be an exception to prove me wrong…) isn’t this solvable with a simple stack?
Read through your string, and every time you have an opening bracket character, you push it into the stack.
When you get a closing bracket character, you peek at the top of the stack and if it matches the closing bracket character, you pop and move on. Otherwise, throw an exception and call it a day.
If you don’t have an empty stack when this is all done, throw an exception then as well.
I’ll think on this some through the week and change my answer if something strikes me, but this is the pre-caffeine answer.
By Gerhard Balthasar on Jul 22, 2008 | Reply
I’ll try my luck:
private static final String open = “([{”;
public static boolean isLegal(String brackets) {
int index;
Stack s = new Stack();
for (char c : brackets.toCharArray()) {
index = open.indexOf(c);
if (index >= 0) s.push((int)c);
index = close.indexOf(c);
if (index >= 0) {
if (s.peek() == open.charAt(index)) s.pop(); else return false;
}
}
return true;
}
Greeting, Gerhard
By Daniel Jimenez on Jul 22, 2008 | Reply
Wouldn’t a simple EBNF do this?
To wit,
Brackets ::= “”
| ”
| ‘(’ Brackets ‘)’
| ‘{’ Brackets ‘}’
| ‘[' Brackets ']‘
This assumes the empty string is a legal pair of (zero) brackets :-).
EBNFs always look so nice, then they’re translated to yacc, or javacc, or antlr, and so much of the elegance is just … lost.
By ilitirit on Jul 22, 2008 | Reply
/* Doesn’t work with escaped chars could possibly made faster by checking if the stack is greater than half the length of the string */
readonly static char [] openers = new char [] { ‘(’, ‘[', '{', '' };
public static bool IsValid(string input)
{
Stack brackets = new Stack(input.Length);
int index;
foreach (char character in input)
{
if ((index = (Array.FindIndex(closers, delegate(char c) { return (c == character); }))) >= 0)
{
if (brackets.Peek() == openers[index])
brackets.Pop();
else
return false;
}
else if (Array.FindIndex(openers, delegate(char c) { return (c == character); }) >= 0)
{
brackets.Push(character);
}
}
return (brackets.Count == 0);
}
By Hugh Brown on Jul 22, 2008 | Reply
See my solution at:
http://www.iwebthereforeiam.com/2008/07/dev102com-programming-challeng-2.html
By Hegi on Jul 22, 2008 | Reply
A rather easy one. It’s classic CS problem.
Most natural option is usage of stack data structure. Whenever we see left bracket of any kind we push in on a stack. Whenever we see right bracket we look what is on top of the stack, if it is matching bracket we pop it. If not, report that strcture is illegal. If there is no bracket to read, than we check whether stack is empty. If so, bracket were placed correctly, otherwise we report illegal structure.
It’s maximum O(n/2) in memory usage.
Perhaps there is a better solution using balance method. Not quite sure how to implemet it for multiple brackets, though.
Using one set of brackets it’s pretty easy. If left bracket increase balance by one. If right than decrase it. If balance drops below zero, than error. At the end baalnce must be equal to 0.
By Sayre on Jul 22, 2008 | Reply
use a stack
By Dejan Dimitrovski on Jul 22, 2008 | Reply
VB solution
Function CheckMatchingBraces(ByVal testString As String) As Boolean
Const OPEN_BRACES As String = “({]”
Dim valid As String = True
Dim stackBraces As New Stack(Of Char)
For Each character As Char In testString.ToCharArray
If OPEN_BRACES.IndexOf(character) > -1 Then
stackBraces.Push(character)
Else
‘a closing brace so the next character in the stack
‘must be the coresponding opening brace
If OPEN_BRACES.Chars(CLOSE_BRACES.IndexOf(character)) stackBraces.Pop Then
Return False
End If
End If
Next
Return True
End Function
One caveat, the closing brace characters in the closing bracket string must be in the same order as the corresponding open braces in the open braces string
By Phi on Jul 22, 2008 | Reply
while( char = readchar()){
if(char.isLeftBracket()) {
stack.push(char)
} else {
if(char != stack.pop()) {
return false
}
}
}
return true
By DaveG on Jul 22, 2008 | Reply
Solution with test cases is posted on my blog. Basic php solution is here:
function brackets ($t) {
$open = ‘({]’;
$fail = (strlen($t)==1);
for ($i=0; (!$fail && $i<strlen($t)); $i++) {
$curr = substr($t,$i,1);
if ( strpos($open, $curr) === false ) {
$fail = ( $i==0 || ( strpos($open,substr($prev,-1)) != strpos($close,$curr) )) ;
if (!$fail) $prev = substr($prev,0,-1);
} else $prev .= $curr;
}
return $fail;
}
By ZagNut on Jul 22, 2008 | Reply
solution at:
http://taotekaching.blogspot.com/2008/07/programming-job-interview-challenge-13.html
thanks,
~zagnut
By Xerxes on Jul 22, 2008 | Reply
Hi - please find my submission for the problem here:
http://www.xerxesb.com/2008/a-programming-job-interview-challenge-13-brackets/
By Arni Hermann on Jul 23, 2008 | Reply
An easy solution comes to mind… You use a stack where you push onto it whenever a specific bracket opens and pop whenever the opposite bracket closes. The resulting stack should be empty or otherwise there’s an illegal state.
By Carl Anderson on Jul 23, 2008 | Reply
One approach: iterate through string pushing left bracket characters onto a stack, and popping off a character when a right character is encountered. If the current character and the popped off character do not form a matching pair, it is not a valid string:
public class Dev102_19 extends TestCase{
public static boolean validate(String s){
if (s==null || s.equals(”"))return false;
Stack stack = new Stack();
for (int i = 0 ; i < s.length() ; i++){
Character c = s.charAt(i);
if (c==’(’ || c==’[' || c=='{' || c=='<'){
stack.push(c);
}
else{
if (stack.size()<1)return false;
Character p = stack.pop();
//if bracket doesn't form a matching pair, it is not valid:
if (p=='(' && c!=')')return false;
if (p=='[' && c!=']‘)return false;
if (p==’{’ && c!=’}')return false;
if (p==”)return false;
}
}
if (stack.size()>0)return false;//valid string will produce an empty stack
return true;
}
public void testValidate(){
assertTrue(validate(”([]())”));
assertTrue(validate(”{}”));
assertTrue(validate(”{{}}”));
assertFalse(validate(”"));
assertFalse(validate(”({}”));
assertFalse(validate(”>>”));
assertFalse(validate(”>”));
assertFalse(validate(”<”));
assertFalse(validate(null));
}
}
By bartek szabat on Jul 23, 2008 | Reply
using System;
using System.Collections.Generic;
using System.Diagnostics;
public static class BracketExpressionValidator
{
private static int[] map = new int[char.MaxValue];
private static int bc = 0;
public static void AddBracketDefinition(char opener, char closer)
{
bc++;
map[opener] = bc;
map[closer] = -bc;
}
static BracketExpressionValidator()
{
AddBracketDefinition(’(', ‘)’);
AddBracketDefinition(’[', ']‘);
AddBracketDefinition(’{', ‘}’);
AddBracketDefinition(”);
}
///
/// Validates brackets expression (see http://www.dev102.com/2008/07/21/a-programming-job-interview-challenge-13-brackets/ )
///
/// brackets expression
/// True is expression is legal, false if expression is illegal
public static bool Validate(string expression)
{
Stack stack = new Stack();
foreach (char c in expression)
{
int code = map[c];
//if (code == 0)
//{
// throw new Exception(”Disallowed character”);
//}
Debug.Assert(code != 0);
if (code > 0)
stack.Push(code);
else
{
if (stack.Count==0 || stack.Pop() != -code)
return false;
}
}
return stack.Count == 0;
}
}
By gav on Jul 23, 2008 | Reply
Solution in F#
http://pastebin.org/56336
By Richard Harrison on Jul 23, 2008 | Reply
I thought about using regular expressions, but honestly I’m not sure what kind of overhead we might have. Also, as the question stated that the input is composed from the bracket characters, no validation occurs within the function I provided. Here is my solution to #13:
private bool AreBracketsValid(string input)
{
const string OPEN = “([{”;
bool result = true;
Stack s = new Stack();
foreach (char c in input)
{
// Push open characters to stack
if (OPEN.Contains(c))
{
s.Push(c);
}
// If close character matches open character, remove open character from stack
else if (OPEN.IndexOf(s.Peek()) == CLOSE.IndexOf(c))
{
s.Pop();
}
// No match, invalid brackets
else
{
result = false;
break;
}
}
return result;
}
By Richard Harrison on Jul 23, 2008 | Reply
Hmmm…okay, some code is getting dropped out when I post it…here’s a URL with the code instead:
http://testing.iontier.com/stuff/Challenge13.txt
By Klemen K. on Jul 24, 2008 | Reply
I think this problem is fairly straight forward, although i’m not sure if it’s the most efficient… You just have to keep track of opening and closing brackets, stack like. If they don’t match up, then we have an illegal expression.
If i take your example:
([]())
i’d go character by character and remember that the first one is opening ‘(’, the second one is opening ‘[', the third one is closing ']‘ which is ok, because the previous first opening (from back forward) was of the same type ‘[’ etc etc
({}
1. opening ‘(’
2. opening ‘{’
3. opening ‘<’
4. closing ‘)’ <- error, because the previous first opening was of a different type
And you can have an optimisation and before going into this checking, just count how many openings and closings there is and if the numbers don’t match up… it’s illegal. But this optimisation wouldn’t work in these two cases.
By Hegi on Jul 24, 2008 | Reply
I’ve put my solution on my newly founded blog. Enjoy!
By Petar Petrov on Jul 24, 2008 | Reply
Here’s my solution:
private static List patterns = new List() { “()”, “[]“, “{}”, “” };
public static bool IsValidExpression(string expression)
{
if (expression.Length > 0)
{
foreach (var p in patterns)
{
var hasValidPattern = expression.Contains(p);
if (hasValidPattern)
{
return IsValidExpression(expression.Replace(p, string.Empty));
}
}
}
return expression.Length == 0;
}
I think this solution meets all requirements ( simple, elegant and efficient).
By Niranjan Viswakarma on Jul 29, 2008 | Reply
Assuming that the different bracket types have no priority among them as such, as is usually the case with mathematical expressions, for e.g u cannot have a ‘{’ within a ‘(’, etc.. i.e, “{a*(b+c)}” is valid while “(a*{b+c})” is not.
Use a counter variable to mimic the operation of a stack.
Start scanning the expression left to right.
Every time a left bracket of any kind, ie ‘(’, ‘{’, ‘[’ or ” is encountered, decrement the counter by 1.
(The Increment stands for the push operation and the Decrement, for the pop operation)
At the end of the expression, if the counter is zero, it is legal. Otherwise, the expression is illegal.
Time Complexity: O(n)
Space Complexity: O(1)
By Michael Dikman on Jul 29, 2008 | Reply
Simple:
Iterating over the input. Putting every opening bracket into a stack. On every closing bracket i dequeue top element from the stack and compare if they match. If they match i go on, otherwise its illegal.
By Chris Marisic on Jul 30, 2008 | Reply
Solution reverse polish simplified parsing http://dotnetchris.wordpress.com/2008/07/30/a-programming-job-interview-challenge-13/
By Alessio Spadaro on Jul 31, 2008 | Reply
If you have a stack available you can push each open bracket and, for each closing bracket, check if it match the top of the stack. If it does, pop the matching bracket. If it doesn’t (either for the wrong bracket or because the stack is empty) the string is illegal.
If at the end of the string the stack is not empty, the string is illegal.
this is linear (O(n)) in both space and time.
A solution with O(1) space would use the input string itself as a stack, using an index for the top of the stack and another to scan the string, with the very same alghoritm.
By Santa on Jul 31, 2008 | Reply
We can use a stack and insert tokens(if it is a opening bracket) or pop tokens(if it is a closing bracket, until a matching opening bracket is popped).
When the end of the expression is encountered we should have the stack empty and at no point during the process we should pop out a null value from the stack.
By Marcos Silva Pereira on Aug 1, 2008 | Reply
Iterate the String:
If you get a opening token put the correspondent token that close in a stack.
If you get a ending token, pop a item from the stack and see if it’s equals to the current token, if not, you get an invalid expression.
Verify, at the end of iteration, if the stack is empty or not. An non empty stack indicates an invalid expression, per instance, “{<[”.
Kind Regards
By Joost Morsink on Aug 4, 2008 | Reply
There was a syntax error in my previous post…
class Program
{
private static Dictionary openClose = new Dictionary { { ‘(’, ‘)’ }, { ” }, { ‘[', ']‘ }, { ‘{’, ‘}’ } };
static void Main(string[] args)
{
Console.WriteLine(IsSyntaxCorrect(args[0]));
}
static bool IsSyntaxCorrect(string s){
var stack=new Stack();
foreach (var ch in s)
if (openClose.ContainsKey(ch))
stack.Push(openClose[ch]);
else if (stack.Count == 0 || stack.Peek() != ch)
return false;
else
stack.Pop();
return true;
}
}
By Arjan Bosma on Aug 7, 2008 | Reply
Not impossible. Just a lot of work to get right.
static bool IsValidExpression(string expression)
{
Regex rxExpression = new Regex(@”^((?{(?.*)})|(?\[(?.*)\])|(?\((?.*)\)))+$”);
bool bReturn = rxExpression.IsMatch(expression);
foreach (Match m in rxExpression.Matches(expression))
{
Capture c = m.Groups["sub"];
if (c.Length > 0)
{
bReturn = IsValidExpression(c.ToString());
if (bReturn == false)
break;
}
}
return (bReturn);
}
By Phil Klein on Aug 19, 2008 | Reply
With nearly every solution utilizing a stack, I thought I’d try and approach the problem differently. Here’s an alternative solution:
public bool ValidateBrackets(string input)
{
string brackets = Regex.Replace(input, @”[^\{\}\[\]\(\)\]+”, String.Empty);
if (brackets.Length % 2 != 0) return false;
else
{
int length;
do
{
length = brackets.Length;
brackets = brackets.Replace(”{}”, String.Empty)
.Replace(”[]“, String.Empty)
.Replace(”()”, String.Empty)
.Replace(”", String.Empty);
} while (length > brackets.Length);
return brackets.Length == 0;
}
}
By Phil Klein on Aug 19, 2008 | Reply
Unfortunately my < and > were removed from my post above. Please take that into account.