Balancing parentheses (),{},[] routine

Question

I have written a simple routine to check if the number of parentheses balances, so [{}] would return true since all parentheses which are opened are closed in the correct order. [)({}] would return false since you cant start with a closing parentheses.

Is anyone able to improve the routine - (efficiency, readability) since I think it works for most cases ?

Here is the code.

public class Compiler { private Stack<char> Stack { get; set; } public string Text { get; set; } private char[] Parentheses { get; set; } public Compiler() { Text = ""; //These are what I classify as parentheses (opening & closing) Parentheses = new char[] { '{', '}', '(', ')', '[', ']' }; Stack = new Stack<char>(); } private bool IsParentheses(char letter) { if (Parentheses.Contains(letter)) { return true; } return false; } public bool IsParenthesesBalanced() { foreach (char letter in Text) { if (IsParentheses(letter)) { if (IsOpeningParentheses(letter)) { //Add to stack Stack.Push(letter); } else if (Stack.Count > 0) { // Stack contains opening parentheses so {,(,[ // We pop elements when we find closing parenthese. char top = Stack.Peek(); if (!IsCorrentClosingParenthese(top, letter)) { return false; } Stack.Pop(); } else { // Stack should we should a opening parenthese otherwise if we // Pop when stack is empty it will throw an error. // This handles when user provide first letter as a closing parenthese // rather then opening so ]()[ return false; } } } if (Stack.Count == 0) { return true; } return false; } private bool IsOpeningParentheses(char parenthese) { int index = Array.IndexOf(Parentheses, parenthese); // All opening parenthese are even position in array - // '{', '}', '(', ')', '[', ']' // 0 1 2 3 4 5 if (index % 2 == 0) { return true; } return false; } private bool IsCorrentClosingParenthese(char openingParenthese, char closingParenthese) { // All matching parenthese it start with opening and next is closing - // '{', '}', '(', ')', '[', ']' // 0 1 2 3 4 5 // We can check if the next openingIndex + 1 position is equal to closingParenthese // In short just check next element. int openingIndex = Array.IndexOf(Parentheses, openingParenthese); if (Parentheses[openingIndex + 1] == closingParenthese) { return true; } return false; } }

Here I am using the class

var compiler = new Compiler(); compiler.Text = @"using System; namespace HelloWorldApplication { class HelloWorld { static void Main(string[] args) { /* my first program in C# */ Console.WriteLine(Hello World); Console.ReadKey(); } } }"; compiler.IsParenthesesBalanced();

No. I dont need to worry about quoted parentheses. Its going to be a code checker. — dijam
– dijam, Commented Aug 25, 2017 at 13:56
...and what if I write "1) Hallo World."? I think you don't know yet that you (need to) care about quotes :-) — t3chb0t
– t3chb0t, Commented Aug 25, 2017 at 14:00
Your right. A string could contain be "1) Hallo World" and the program will think its syntax so it needs a closing parentheses. — dijam
– dijam, Commented Aug 25, 2017 at 14:05

Heslacher · Accepted Answer · 2017-08-28 07:01:03Z

I think you can make a few improvements that will make this class not only more useful but also easier to understand.

I'd start with naming the class according to its job, which is ParenthesesValidator. Then the main method becomes ValidateParenthesesBalanced. The next step is to throw away the constructor and the Text property. It doesn't have to be the state of the class. You can perfectly pass it to the validating method. The same with the Stack. What can be local to a method should be local. This way you can make less mistakes by overwriting the data and contribute to the thread-safety of the validation.

Then let's take care of the definition of the parentheses that currently is an array:

Parentheses = new char[] { '{', '}', '(', ')', '[', ']' };

This requries some computations to find the matchin paretheses but there is another way. With the new tuples you can define a few helper variables that will allow you to greatly simplify the logic.

private static readonly IEnumerable<(char Opening, char Closing)> Parentheses = new (char, char)[] { ('{', '}'), ('(', ')'), ('[', ']') }; private static readonly ISet<char> OpeningParentheses = new HashSet<char>(Parentheses.Select(p => p.Opening)); private static readonly ISet<char> ClosingParentheses = new HashSet<char>(Parentheses.Select(p => p.Closing)); private static readonly ISet<char> AllParentheses = new HashSet<char>(OpeningParentheses.Concat(ClosingParentheses)); private static readonly IDictionary<char, char> ParenthesesMap = Parentheses.ToDictionary(p => p.Opening, p => p.Closing);

You first create a collection of all Parentheses naming them as Opening and Closing. You use it to build the other helper collections. Using hash-sets is usually faster then scanning arrays because it is an O(1) operation unlike the O(n) with an array. Lastly you create a dictionary that will map an opening paretheses to a closing one so you don't have to compute anything.

With this optimization your code becomes two one-liners:

private bool IsParentheses(char letter) { return AllParentheses.Contains(letter); } private bool IsCorrectClosingParenthese(char openingParenthese, char closingParenthese) { return ParenthesesMap[openingParenthese] == closingParenthese; }

You can also remove this condition

if (IsParentheses(letter))

by plugging this method into a Where behind the text

foreach (char letter in text.Where(IsParentheses))

After putting everything together your code would look like this:

public class ParenthesesValidator { private static readonly IEnumerable<(char Opening, char Closing)> Parentheses = new (char, char)[] { ('{', '}'), ('(', ')'), ('[', ']') }; private static readonly ISet<char> OpeningParentheses = new HashSet<char>(Parentheses.Select(p => p.Opening)); private static readonly ISet<char> ClosingParentheses = new HashSet<char>(Parentheses.Select(p => p.Closing)); private static readonly ISet<char> AllParentheses = new HashSet<char>(OpeningParentheses.Concat(ClosingParentheses)); private static readonly IDictionary<char, char> ParenthesesMap = Parentheses.ToDictionary(p => p.Opening, p => p.Closing); public bool ValidateParenthesesBalanced(string text) { var stack = new Stack<char>(); foreach (char letter in text.Where(IsParentheses)) { if (OpeningParentheses.Contains(letter)) { stack.Push(letter); } else if (stack.Count > 0) { // Stack contains opening parentheses so {,(,[ // We pop elements when we find closing parenthese. var top = stack.Peek(); if (!IsCorrectClosingParenthese(top, letter)) { return false; } stack.Pop(); } else { // Stack should we should a opening parenthese otherwise if we // Pop when stack is empty it will throw an error. // This handles when user provide first letter as a closing parenthese // rather then opening so ]()[ return false; } } return stack.Count == 0; } private bool IsParentheses(char letter) { return AllParentheses.Contains(letter); } private bool IsCorrectClosingParenthese(char openingParenthese, char closingParenthese) { return ParenthesesMap[openingParenthese] == closingParenthese; } }

Additionally you can easily fix the quoted text and skip it by adding a small helper method to the class:

private static IEnumerable<char> SkipQuoted(IEnumerable<char> chars) { var escapeMode = false; foreach (var c in chars) { if (c == '"' && !escapeMode) { escapeMode = true; continue; } if (escapeMode) { if (c == '"') { escapeMode = false; } continue; } yield return c; } }

You then pass the text first to this method before grabbing the paretheses:

foreach (char letter in SkipQuoted(text).Where(IsParentheses))

Looks like the foreach loop in the SkipQuoted method could be simplified to foreach (var c in chars) { if (c == '"') { escapeMode = !escapeMode; continue; } yield return c; }. However, both methods only handle the case of a simple string. A string with an escaped quotation mark ("\"") and a string using string interpolation ($"This is an interpolated {typeof(string).Name}.") would both fail. — Jaquez
– Jaquez, Commented Aug 26, 2017 at 3:54
@Jaquez oh, you're so right and on the other hand it's just an example ;-) — t3chb0t
– t3chb0t, Commented Aug 26, 2017 at 6:56
Totally. Just wanted to point it out so that someone didn't try to blindly use it somewhere. Not that that EVER happens to code here. ;-) The rest of the review is spot on and better than I would have come up with. Definitely a +1 from me. — Jaquez
– Jaquez, Commented Aug 27, 2017 at 3:35

Maxim · Accepted Answer · 2017-08-25 14:02:26Z

This

private Stack<char> Stack { get; set; } public string Text { get; set; } private char[] Parentheses { get; set; } public Compiler() { Text = ""; //These are what I classify as parentheses (opening & closing) Parentheses = new char[] { '{', '}', '(', ')', '[', ']' }; Stack = new Stack<char>(); }

can be rewritten as

private Stack<char> Stack { get; } = new Stack<char>(); public string Text { get; set; } = string.Empty; private char[] Parentheses { get; } = new char[] { '{', '}', '(', ')', '[', ']' };

Code like this

if (Parentheses.Contains(letter)) { return true; } return false;

can be simplified to

return Parentheses.Contains(letter);

These checks

Stack.Count > 0 Stack.Count == 0

can be changed to

Stack.Any() !Stack.Any()

Stack Exchange Network

Balancing parentheses (),{},[] routine

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Balancing parentheses (),{},[] routine

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions