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

## Comments

## Post a Comment