3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Are you checking for just balance or proper nesting and balance? \$\endgroup\$ – tinstaafl Jan 5 '18 at 4:40
  • \$\begingroup\$ @tinstaafl looking at the fifth test case it looks like nesting and balance \$\endgroup\$ – Heslacher Jan 5 '18 at 5:03
  • 1
    \$\begingroup\$ That's the usual case, but the OP isn't being explicit about it. \$\endgroup\$ – tinstaafl Jan 5 '18 at 5:08
5
\$\begingroup\$

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();
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Rick Davin Jan 5 '18 at 12:01
  • \$\begingroup\$ Agreed on bracketIndex and edited. currentStack needs to be declared outside of the loop. \$\endgroup\$ – Heslacher Jan 5 '18 at 12:27
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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();
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.