The.
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 -.
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.
We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
sirrocco Said on Jul 21, 2008 :
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
Omar Said on Jul 21, 2008 :
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;
Jason Kikel Said on Jul 21, 2008 :
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.
Mark R Said on Jul 21, 2008 :.
Mark R Said on Jul 21, 2008 :
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.
Trinity Said on Jul 21, 2008 :
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.
James Curran Said on Jul 21, 2008 :
My solution is posted here:
(So, am I the first with full code?)
Justin Etheredge Said on Jul 21, 2008 :
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;
Michael Mrozek Said on Jul 21, 2008 :
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
Nate Said on Jul 21, 2008 :
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);
}
}
}
Kevin Hjelden Said on Jul 21, 2008 :
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;
}
Jeremy Weiskotten Said on Jul 21, 2008 :
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.
hi Said on Jul 21, 2008 :
Alex Said on Jul 21, 2008 :
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.
S Javeed Said on Jul 21, 2008 :
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 {
}
}
}
$status = 0 if (@stack);
return $status;
}
while (my $line = ) {
chomp $line;
my $result = checkBrackets($line);
print “$line: ” . ($result ? “LEGAL” : “ILLEGAL”) . “\n”;
}
Steven Baker Said on Jul 21, 2008 :
easily done with a stack
leppie Said on Jul 22, 2008 :
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.
Morgan Cheng Said on Jul 22, 2008 :
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);
}
Hello world Said on Jul 22, 2008 :
#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;
}
Liming Zhang Said on Jul 22, 2008 :
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.
herval Said on Jul 22, 2008 :
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
Samuel Williams Said on Jul 22, 2008 :
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)
dextar Said on Jul 22, 2008 :
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
dextar Said on Jul 22, 2008 :
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
macmariman Said on Jul 22, 2008 :
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.
Haskell programmer Said on Jul 22, 2008 :
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”
Darrell Wright Said on Jul 22, 2008 :
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;
}
Ryan Said on Jul 22, 2008 :
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.
Shams Mahmood Said on Jul 22, 2008 :
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 == ‘}’)
);
}
Kimmen Said on Jul 22, 2008 :
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;
}
Terje Myklebust Said on Jul 22, 2008 :
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;
}
Jelle Hissink Said on Jul 22, 2008 :
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…
}
Matt Howells Said on Jul 22, 2008 :
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.
Dave Amphlett Said on Jul 22, 2008 :
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);
}
}
levi Said on Jul 22, 2008 :
This is in Java:
levi_h Said on Jul 22, 2008 :
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:
Mark Brackett Said on Jul 22, 2008 :
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) {
} else {
// close or invalid token
if (CLOSE[openTokens.Pop()) != c) {
throw new InvalidFormatException();
}
}
}
configurator Said on Jul 22, 2008 :
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)
Tim Kington Said on Jul 22, 2008 :
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.
valera Said on Jul 22, 2008 :
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)
Christof Jans Said on Jul 22, 2008 :
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;
}
Mike G. Said on Jul 22, 2008 :
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”}’
Michael Said on Jul 22, 2008 :
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”)));
}
}
Mike G. Said on Jul 22, 2008 :
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.
Charles Said on Jul 22, 2008 :
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
Mike G. Said on Jul 22, 2008 :
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.
Jon von Gillern Said on Jul 22, 2008 :
Thanks!
Richard Vasquez Said on Jul 22, 2008 :
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.
Gerhard Balthasar Said on Jul 22, 2008 :
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
Daniel Jimenez Said on Jul 22, 2008 :
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.
ilitirit Said on Jul 22, 2008 :
/* 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);
}
Hugh Brown Said on Jul 22, 2008 :
See my solution at:
Hegi Said on Jul 22, 2008 :
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.
Sayre Said on Jul 22, 2008 :
use a stack
Dejan Dimitrovski Said on Jul 22, 2008 :
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
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
Phi Said on Jul 22, 2008 :
while( char = readchar()){
if(char.isLeftBracket()) {
stack.push(char)
} else {
if(char != stack.pop()) {
return false
}
}
}
return true
DaveG Said on Jul 22, 2008 :
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;
}
ZagNut Said on Jul 22, 2008 :
solution at:
thanks,
~zagnut
Xerxes Said on Jul 22, 2008 :
Hi - please find my submission for the problem here:
Arni Hermann Said on Jul 23, 2008 :
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.
Carl Anderson Said on Jul 23, 2008 :
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));
}
}
bartek szabat Said on Jul 23, 2008 :
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 )
///
/// 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;
}
}
gav Said on Jul 23, 2008 :
Solution in F#
Richard Harrison Said on Jul 23, 2008 :
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;
}
Richard Harrison Said on Jul 23, 2008 :
Hmmm…okay, some code is getting dropped out when I post it…here’s a URL with the code instead:
Klemen K. Said on Jul 24, 2008 :
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.
Hegi Said on Jul 24, 2008 :
I’ve put my solution on my newly founded blog. Enjoy!
Petar Petrov Said on Jul 24, 2008 :
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).
Niranjan Viswakarma Said on Jul 29, 2008 :
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)
Michael Dikman Said on Jul 29, 2008 :
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.
Chris Marisic Said on Jul 30, 2008 :
Solution reverse polish simplified parsing
Alessio Spadaro Said on Jul 31, 2008 :
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.
Santa Said on Jul 31, 2008 :
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.
Marcos Silva Pereira Said on Aug 1, 2008 :
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
Joost Morsink Said on Aug 4, 2008 :
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;
}
}
Arjan Bosma Said on Aug 7, 2008 :
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);
}
Phil Klein Said on Aug 19, 2008 :
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;
}
}
Phil Klein Said on Aug 19, 2008 :
Unfortunately my < and > were removed from my post above. Please take that into account.
Joseph Porter Said on Dec 27, 2008 :
If you’re looking for some other good programming interview questions, check out: