Check if a string contains matching brackets

Question

Trying to solve a case for a set of multiple types of brackets.

class BracketHelper {
 // checks if the string contains properly formatted brackets
 public static bool ProperBrackets(string s) {
 int p = 0;
 return ProperBrackets(s.ToCharArray(), ref p);
 }
 // main method, uses recursion to check if the brackets are properly formatted
 private static bool ProperBrackets(char[] arr, ref int ptr, char oppBracket = ' ') {
 for(;ptr<arr.Length;ptr++) {
 var ch = arr[ptr];
 if ( IsOpen(ch)) { // found an open bracket - let's check the inner content
 ptr +=1; // start checking from the next position
 if (ProperBrackets(arr, ref ptr, OppositeOf(ch)) == false) // inner content is malformed?
 return false;
 }
 if ( IsClose(ch) ) // found a closing bracket
 return ch == oppBracket; // is this what we were looking for? If not - then we found a malformity!
 }
 // we reached the end. are we still searching for the closing bracket?
 return oppBracket == ' ';
 }
 private static char[] OpenBrackets = new char[] { '{', '[', '(' };
 private static char[] CloseBrackets = new char[] { '}', ']', ')' };
 // check helpers
 private static bool IsOpen(char ch) { return OpenBrackets.Contains(ch); }
 private static bool IsClose(char ch) { return CloseBrackets.Contains(ch); }
 // returns a closing bracket character
 private static char OppositeOf(char ch) {
 for(var i=0;i<OpenBrackets.Length;i+=1)
 if ( ch == OpenBrackets[i] ) 
 return CloseBrackets[i];
 throw new Exception($"'{ch}' is not an open bracket");
 }
}

Some test cases for LinqPad:

(BracketHelper.ProperBrackets("{}") == true).Dump();
(BracketHelper.ProperBrackets("{[]()}") == true).Dump();
(BracketHelper.ProperBrackets("{[()][{}]{}}") == true).Dump();
(BracketHelper.ProperBrackets("{[}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[{(}])}") == false).Dump();
(BracketHelper.ProperBrackets("{[][][][{(})}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[]}}") == false).Dump();
(BracketHelper.ProperBrackets("{") == false).Dump();

This can be done with the ref argument, so the pointer is a member of a class but in this case the method won't be static and I just wanted to make its usage as convenient as possible.

• user33306: Are you checking for just balance or proper nesting and balance?
• Heslacher: @tinstaafl looking at the fifth test case it looks like nesting and balance
• user33306: That's the usual case, but the OP isn't being explicit about it.

Answer 1

Let's first take a look at the code

• The code could use some space to breathe by adding spaces before and after operators. For example for(;ptr<arr.Length;ptr++) would be more readable like
  for (; ptr < arr.Length; ptr++)
• The expected bracing style would be to place an opening bracket on a new line.
• Omitting braces {} although they might be optional can lead to hidden and therefor hard to find bugs. I would like to encourage you to always use them.
• Comments should describe why something is done. Comments like if ( IsClose(ch) ) // found a closing bracket are superflous and reduce the readability of the code.
• I know that naming things is a hard task but one should at least try to do this in a way that a reader of the code can grasp the meaning of a variable fast which isn'tthe case for oppBracket. If a method returns a bool one should name that method like a question. E.g AreBracketsProper would be a better name.

---

Using recursion is a way one can use, but recursion isn't the holy grail for such a task. You need a ref int and an optional oppBracket to achieve the goal by using recursion.

I would use a Stack<Stack<T>> for keeping track of the nesting levels and instead of two char[] arrays I would use two strings and would use IndexOf(char) to get the index of a bracket and to check if the current char is a bracket at all.

If I find an opening bracket I will create a new Stack<int> which contains the value of openingBrackets.IndexOf() and then I will Push() it on the Stack<Stack<int>>. If I find an closing bracket I will take the last index from the Stack<int> if ther is any and check if it is the same as the value returned from closingBrackets.IndexOf(). This coul truned into an extension method as well, like so

static class BracketHelper
{
 private const string openingBrackets = "{[(";
 private const string closingBrackets = "}])";
 public static bool AreBracketsProper(this string value)
 {
 if (value == null) { throw new ArgumentNullException(nameof(value)); }
 if (string.IsNullOrWhiteSpace(value)) { return true; }
 var stacks = new Stack<Stack<int>>();
 var currentStack = new Stack<int>();
 foreach (char c in value)
 {
 var bracketIndex = 0;
 if ((bracketIndex = openingBrackets.IndexOf(c)) > -1)
 {
 currentStack = new Stack<int>();
 currentStack.Push(bracketIndex);
 stacks.Push(currentStack);
 }
 else if ((bracketIndex = closingBrackets.IndexOf(c)) > -1)
 {
 while (currentStack.Count == 0 && stacks.Count > 0)
 {
 currentStack = stacks.Pop();
 }
 if (currentStack.Count == 0 || bracketIndex != currentStack.Pop()) { return false; }
 }
 }
 return stacks.Count == 0 || stacks.Pop().Count == 0;
 }
}

Which could be called as an extension method like so

("{}".AreBracketsProper() == true).Dump();
("{[]()}".AreBracketsProper() == true).Dump();
("{[()][{}]{}}".AreBracketsProper() == true).Dump();
("{[}]}".AreBracketsProper() == false).Dump();
("{[{(}])}".AreBracketsProper() == false).Dump();
("{[][][][{(})}]}".AreBracketsProper() == false).Dump();
("{[]}}".AreBracketsProper() == false).Dump();
("{".AreBracketsProper() == false).Dump();
("}".AreBracketsProper() == false).Dump();

• Rick Davin: I really like this answer and the explanation. Suggestion: you could move the declaration for bracketIndex and currentStack to be inside the foreach since that seems to be the limit of their scope.
• Heslacher: Agreed on bracketIndex and edited. currentStack needs to be declared outside of the loop.

Answer 2

I totally agree with the points made by Heslacher:

• You should not omit brackets
• Better naming leads you to need less comments
• Comments should explain why if the code is not explicit

also:

• You should add some parameter validation since it's going to be a public method, every public method should validate its parameters before doing any job.

I also think this is such a simple task, no need to use recursion. I would use a Dictionary<char, char> to map each opening bracket with its closing bracket, have a HashSet<char> for closing brackets check purpose and a Stack<char> to push each opening bracket and pop its closing bracket. In case there is a closing bracket mismatch returns false, in the end if there are still open brackets in the stack, it means there are brackets mismatch:

private static readonly Dictionary<char, char> brackets = new Dictionary<char, char>() {
 { '(', ')' },
 { '[', ']' },
 { '{', '}' }
};
private static readonly HashSet<char> closingBrackets = new HashSet<char>(brackets.Values);
public static bool AreBracketsProper(string value)
{
 if (value == null)
 {
 throw new ArgumentNullException(nameof(value));
 }
 if (value.Length == 0)
 {
 return true;
 }
 var openBrackets = new Stack<char>();
 foreach (char chr in value)
 {
 if (brackets.ContainsKey(chr))
 {
 openBrackets.Push(chr);
 continue;
 }
 if (!closingBrackets.Contains(chr))
 {
 continue;
 }
 if (openBrackets.Count == 0 || brackets[openBrackets.Peek()] != chr)
 {
 return false;
 }
 openBrackets.Pop();
 }
 return openBrackets.Count == 0;
}

I would not make it an extension though, because I think it would pollute string methods with a kind of specific functionality.

I am also assuming that no brackets means they are proper.

Answer 3

The general issues in your code have already been mentioned in other answers so I'll just post a simpler solution.

---

You only need a single stack where you put all the left/opening brackets. When you find a right/closing bracket you pop a left one from the stack. If it doesn't match the current right bracket then you know they are not balanced. It works with all your test cases.

public static bool Balanced(this string value)
{
 var openingBrackets = new Stack<char>();
 foreach (var c in value)
 {
 switch (c)
 {
 case '(':
 case '[':
 case '{':
 openingBrackets.Push(c);
 break;
 case ')': if (!TryPop(out var openingRound) || openingRound != '(') return false; break;
 case ']': if (!TryPop(out var openingSquare) || openingSquare != '[') return false; break;
 case '}': if (!TryPop(out var openingCurly) || openingCurly != '{') return false; break;
 }
 }
 return !openingBrackets.Any();
 bool TryPop(out char opening)
 {
 if (openingBrackets.Any())
 {
 opening = openingBrackets.Pop();
 return true;
 }
 else
 {
 opening = '0円';
 return false;
 }
 }
}

---

(BracketHelper.ProperBrackets("{}") == true).Dump();
(BracketHelper.ProperBrackets("{[]()}") == true).Dump();
(BracketHelper.ProperBrackets("{[()][{}]{}}") == true).Dump();
(BracketHelper.ProperBrackets("{[}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[{(}])}") == false).Dump();
(BracketHelper.ProperBrackets("{[][][][{(})}]}") == false).Dump();
(BracketHelper.ProperBrackets("{[]}}") == false).Dump();
(BracketHelper.ProperBrackets("{") == false).Dump();

I don't like your test cases because it's too much copy/paste. Creating an array with test-cases and expected results would simplify it.

var data = new (string TestCase, bool Balanced)[]
{
 ("{}", true),
 ("{[]()}", true),
 ("{[()][{}]{}}", true),
 ("{[}]}", false),
 ("{[{(}])}", false),
 ("{[][][][{(})}]}", false),
 ("{[]}}", false),
 ("{", false)
};
data.Select(x => (x.TestCase.Balanced() == x.Balanced)).Dump();