How to check if nested brackets are in the correct logical order

I am starting a series of blog posts on algorithms and data structures with the first one being the easiest!

Q. Write a method that checks if the nested brackets are in the correct logical order. The input string is the following:

“{ [ () {} ] }”

Please note, there can be many interpretations, but here’s how I am attempting to solve this question which may not necessarily be the most efficient solution. Here it goes…

First off, I create a console app and write a function that removes erroneous spaces like so:

 
        public static String FilterErroneousChars(String input)
        {
            int len = input.Length;
            char[] arr = input.ToCharArray();
            String filter = "";
            for (int i = 0; i < len; i++)
            {
                if (arr[i].Equals('(') || arr[i].Equals(')') || arr[i].Equals('[') || arr[i].Equals(']') || arr[i].Equals('{') || arr[i].Equals('}'))
                {
                    filter += arr[i];
                }
            }
            return filter;
        }

Once the function is executed, it’ll return a string with no spaces, i.e. “{[(){}]}”.

Next, I call the method from Program Main() and pass in the compressed string as input like so:

Then, I check to see if any of the nested pair(s) is equal. If the condition is met, the program replaces the nested brackets with an empty string until there’s nothing left.

In the end, I check to see if the length of the string is 0. Once this condition evaluates to True, we know, that the input string is well-formed, else NOT.

I hope, those of you that are new to data structures, you might find this algorithmic exercise useful.

String s = Algorithms.FilterErroneousChars("{ [ () {} ] }");
            while ((s.Length != 0) && (s.Contains("[]") || s.Contains("()") || s.Contains("{}")))
            {
                s = s.Replace("[]", "");
                s = s.Replace("()", "");
                s = s.Replace("{}", "");
            }

            if (s.Length == 0)
            {
                Console.WriteLine("Well Formed");
            }
            else
            {
                Console.WriteLine("Not Well Formed");
            }

About Obi Oberoi

Obi Oberoi is a Microsoft MVP (Visual Studio & Development Technologies), developer and a life-long student of continuous learning. Obi enjoys to code, read, and hang out with techies and geeks!
This entry was posted in Algorithms & Data Structures. Bookmark the permalink.