Validating balanced parenthesis, brackets and braces inside a mathematical equation.

Today, I will try to create a C# method that would validate if the brakcets, parenthesis and braces of a given mathematical equation is properly written, balanced and complete. The goal of this excercise is to utilize the stack data structure to write an algorithm with a linear growth. Any suggestions on how to do this using logarithmic algorithms are welcome.

The method should return true for the following inputs:

  • (x + y) - ((z * y) + x)
  • {(1 / 2) + (y / z)} - ([g + z]) - (x + y)
  • [x + y] - (5 * x)

The method should return false for the following inputs:

  • (x + 3]
  • {(y + z)]
  • (x + y) + [g(5])]

Solution


Clone it from GitHub
Below is a class that validates if the brackets, parenthesis and curly braces of a formula are properly written and has a counterpart.

The class uses an instance of the native Dictionary class to identify pairs of opening and closing brackets, braces and parenthesis.

The class have also utilized the native Stack class to store (PUSH) opening brackets that it encounters. For every closing bracket that it encounters, it removes (POP) the last inserted character from the stack if it is a proper match. Otherwise, it terminates the method execution and returns false since an anomaly in the formula has been identified.

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

namespace Stacking101.BracketMatching
{
    public class FormulaValidator
    {
        // Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
        // { [ ( } ] )
        // Example: "()" is balanced
        // Example: "{ ]" is not balanced.
        // Examples: "()[]{}" is balanced.
        // "{([])}" is balanced
        // "{ ( [ ) ] }" is _not_ balanced
        // Input: string, containing the bracket symbols only
        // Output: true or false
        public bool IsBalanced(string input)
        {
            var brackets = BuildBracketMap();
            var openingBraces = new Stack();
            var inputCharacters = input.ToCharArray();
            foreach (char character in inputCharacters)
            {
                if (brackets.ContainsKey(character))
                {
                    openingBraces.Push(character);
                }
                if (brackets.ContainsValue(character))
                {
                    var closingBracket = character;
                    var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;
                    if (openingBraces.Peek() == openingBracket)
                        openingBraces.Pop();
                    else
                        return false;
                }
        }

        private Dictionary<char, char> BuildBracketMap()
        {
            return new Dictionary<char, char>()
            {
                {'[', ']'},
                {'(', ')'},
                {'{', '}'}
            };
        }
    }
}

Testing the Solution

using Stacking101.BracketMatching;
using System;

namespace Stacking101
{
    class Program
    {
        static void Main(string[] args)
        {
            var testData = new string[] {
                "(x + y) - ((z * y) + x)",
                "{(1 / 2) + (y / z)} - ([g + z]) - (x + y)",
                "[x + y] - (5 * x)",
                "(x + 3]",
                "{(y + z)]",
                "(x + y) + [g(5])]"
            };
            var formulaValidator = new FormulaValidator();

            foreach(var equation in testData)
            {
                Console.WriteLine(
                    string.Format("{0} {1}", equation, formulaValidator.IsBalanced(equation))
                );
            }

            Console.ReadKey();
        }
    }
}

Output


Comments

Popular posts from this blog

Building Simple API Gateways with Ocelot and ASP.net Core

API Gateway in a Nutshell

Replicating Netflix Part 1: Installing Raspbian Lite using Etcher

10 Steps to Setup and Containerize an Express Server