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));
 }
}

• Rick Davin: For a simple balanced pair check without temporary lists, you can (1) move up from last known Left index until you find an opening bracket, (2) determine the required closing bracket, and (3) from last known Right index move down looking for ANY closing bracket. If that bracket is not found or is not the required closing bracket, you may return false and stop processing. You also stop when the last known Left index is no longer less than the Right index.
• BCdotWEB: FYI Your code doesn't follow the naming guidelines: docs.microsoft.com/en-us/dotnet/standard/design-guidelines/…
• aldo: @RickDavin But then with your algortihm, wouldn't ({[)}] be a valid answer, while it is actually not?
• Rick Davin: No. Re-read: move down looking for ANY closing bracket. If that bracket is not found or is not the required closing bracket, you may return false.

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.

• aldo: Wow yeah a dictionary is more suitable since the brackets can be thought of as a key-pair . Thanks for the reply!
• Bobby J: When the input contains excess closing bracket, this code crashes because pop from empty stack.
• Alexey Nis: @BobbyJ, you right! My mistake. Thank you!
• raznagul: The variable i makes this very confusing to read. The variable should have a better name, or at least on that isn't associated with the index of a for loop. Also the formatting is very inconsistent. There are 5 if statements and the use of braces in line breaks is different for all of them.
• raznagul: Also, while the algorithm is good, this answer doesn't give any feedback about OPs original code.

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;