C# code to check balanced brackets in a string

Question

The code works, at least against the unit tests. But I would like input on how to refactor it. Or also maybe a way to do this without using temporary lists? I also have some special checks, like if the string is empty or if the brackets are unbalanced; is there a way to incorporate these special checks into the main body? It has been my problem with coding; I cannot refactor special cases into the general algorithm.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public static class MatchingBrackets
{
    public static bool IsPaired(string input)
    {
        string opening = "{[(";
        string closing = "}])";
        // Temporary lists to hold currently unmatched opening-closing brackets
        List<char> opening_brackets = new List<char>{};
        List<char> closing_brackets = new List<char>{};
        // If input is empty string then return true
        if (input.Count() == 0) { return true;}
        // Loop through each character
        foreach (char i in input)
        {
            // If the character is in the set of opening and closing brackets
            if ((opening + closing).Contains(i))
                // If it is an opening bracket, append to opening brackets temp list
                if (opening.Contains(i) is true) { opening_brackets.Add(i); }
                else
                {
                    // Append closing bracket to closing brackets temp list
                    closing_brackets.Add(i);
                    // If there are no (more) temp opening brackets but we are in this else statement,
                    // then we fail already
                    if (opening_brackets.Count == 0) { return false;}
                    // Find the opening bracket that corresponds to the currently closing bracket
                    char required_prev_opening = opening.ElementAt(closing.LastIndexOf(i));
                    // If the corresponding opening bracket is not the same to the last 
                    // opening bracket, we fail already
                    if (required_prev_opening != (char)opening_brackets.Last()) { return false;}
                    // The current closing bracket has a correct corresponding opening bracket. Remove them from
                    // their respective temporary list
                    opening_brackets.RemoveAt(opening_brackets.Count-1);
                    closing_brackets.RemoveAt(closing_brackets.Count-1);
                }
        }
        // Check if there are still unmatched opening or closing brackets. If so then we fail.
        if (opening_brackets.Count != 0 || closing_brackets.Count != 0)
        {
            return false;
        }
        return true;
    }
}

The unit tests are:

// This file was auto-generated based on version 2.0.0 of the canonical data.

using Xunit;

public class MatchingBracketsTests
{
    [Fact]
    public void Paired_square_brackets()
    {
        var value = "[]";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Empty_string()
    {
        var value = "";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Unpaired_brackets()
    {
        var value = "[[";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Wrong_ordered_brackets()
    {
        var value = "}{";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Wrong_closing_bracket()
    {
        var value = "{]";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Paired_with_whitespace()
    {
        var value = "{ }";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Partially_paired_brackets()
    {
        var value = "{[])";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Simple_nested_brackets()
    {
        var value = "{[]}";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Several_paired_brackets()
    {
        var value = "{}[]";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Paired_and_nested_brackets()
    {
        var value = "([{}({}[])])";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Unopened_closing_brackets()
    {
        var value = "{[)][]}";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Unpaired_and_nested_brackets()
    {
        var value = "([{])";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Paired_and_wrong_nested_brackets()
    {
        var value = "[({]})";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Paired_and_incomplete_brackets()
    {
        var value = "{}[";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Too_many_closing_brackets()
    {
        var value = "[]]";
        Assert.False(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Math_expression()
    {
        var value = "(((185 + 223.85) * 15) - 543)/2";
        Assert.True(MatchingBrackets.IsPaired(value));
    }

    [Fact]
    public void Complex_latex_expression()
    {
        var value = "\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \\end{array}\\right)";
        Assert.True(MatchingBrackets.IsPaired(value));
    }
}

Answer 1

Nice code. But you can use one stack instead two lists. Try to refactor your code. Push the opening bracket to the stack. Pop the last bracket. In case there is wrong bracket return false.

At the end you should get empty stack in case the brackets are paired

public static class MatchingBrackets
{
    private static Dictionary<char, char> _pairs = new Dictionary<char, char> 
    {
        { '(', ')' },
        { '[', ']' },
        { '{', '}' },
    };
    public static bool IsPaired(string input)
    {

        // If input is empty string then return true
        if (input.Count() == 0) { return true;}

        Stack<char> brackets = new Stack<char>();

        // Loop through each character
        foreach (char i in input)
        {
            // If it is an opening bracket, push it to the stack
            if(_pairs.ContainsKey(i)){
                brackets.Push(i);
            }
            // If it is an closing bracket, pop it
            else if(_pairs.Values.Contains(i))
            {
                if(brackets.Count == 0) return false;

                var openingBracket = brackets.Pop();
                // If it isn't pair of the last opening bracket return false
                if(_pairs[openingBracket] != i) 
                {
                    return false;
                }
            }
        }
        // The stack should be empty in case all brackets are closed
        return brackets.Count == 0;
    }
}

Try it out yourself.

Answer 2

Too many comments

Comments should only be used when absolutelly necessary to explain why something is done. What is done doesn't belong in comments, as this should be clear from reading the code.

// If input is empty string then return true
if (input.Count() == 0) { return true;}

This comment for example doesn't add anything and just makes it harder to read the code.

Naming

Be consistent! IsPaired uses PascalCase while the methods in the unit test use Snake_case.

Also use descriptive names. Most of your names are very good but the i in the loop shoud get a better name. i is associated with the index variable in for loops and should only be used there. When ready the code I actually go confused once about where the index in coming from.

Use of braces

There should be braces after if ((opening + closing).Contains(i)). Especially as ther is a lot of code.
Also there should be a space before the closing braces in the single line ifs.

closing_brackets is uncessary

After adding items to this list the method either returns or removes the just added item. So this list does nothing.

input.Count() is problematic on many levels

You don't have a unit test with a null string as input. This case will fail with a NullReferenceException at input.Count().
Also .Count() is not a member of the string type. But an extensions method from Linq. It would be better to use the Length property instead.

But I think it would be best to change the condition to

if(string.IsNullOrEmpty(input))

Directly use the bool result of methods

The is true in if (opening.Contains(i) is true) is unnecessary.

The nested ifs in the loop are unncessary

Generally avoid unecessary nesting. You mostly do this by exiting early from the loop.

This code

if ((opening + closing).Contains(i))
    if (opening.Contains(i) is true) { opening_brackets.Add(i); }
    else
    {

can be changed to

if (opening.Contains(i))
{
    opening_brackets.Add(i);
}
else if (closing.Contains(i))
{

You can directly return the result of boolean operations

The last if can be replaced by a return statement, especially if you get rid of the closing_brackets list.

return opening_brackets.Count == 0;