Checking for** balanced parentheses **or

**is a very old and classic problem in the field of computer science.**

*balanced brackets*As we all know there are three kinds of parentheses or brackets. They are the *round brackets*, the *curly brackets* and the *square brackets*. Each of the brackets has an opening part and a closing part.

Now the question arises — what are balanced parentheses? Some parentheses are called balanced if each opening bracket has a corresponding closing bracket or each closing bracket has a corresponding opening bracket and the brackets are properly nested. Followings are some examples of balanced parentheses:

```
()
()()()
((()))
{()}
[[[{{((()))}}]]]
[][]()(){()}{}
```

And the followings are some example of parentheses which are not balanced:

```
()))
)))(((
{()()
[[[}}}
{}{
```

Now, let’s try to make an algorithm with the stack. But why stack? To understand this, we have to pay a closer look at the parentheses balancing. Some parentheses are balanced only if there is a corresponding closing part of a specific parenthesis’s opening part in sequence. Consider a string of balanced parentheses as “** [{()}]**”. Here, the opening parentheses are “

**”. So to be balanced “**

*[{(***” has to come first, then “**

*)***” and “**

*}***” respectively. If we add the opening parts to the stack, it’ll be done as follows:**

*]*Now, when the closing part comes, if it matches the corresponding opening part, it indicates that it is a balancing part and the parenthesis is removed from the stack. It works as follows:

Thus if after processing the string if the stack is empty, the parentheses are balanced.

A CPP implementation of checking parentheses balance is as follows:

```
bool isBalanced(string expression){
stack <char> s;
for(int i = 0; i < expression.length(); i++){
if(expression[i] == '(' || expression[i] == '{' || expression[i] == '['){
s.push(expression[i]);
continue;
}
if(s.empty())
return false;
char c = s.top();
switch(expression[i]){
case ')':
if(c != '(')
return false;
break;
case '}':
if(c != '{')
return false;
break;
case ']':
if(c != '[')
return false;
break;
default:
break;
}
s.pop();
}
return s.empty();
}
```

You can get the full implementation here. If you like a video version. Check here. Thank you very much.

April 15, 2020

Like it!?

April 15, 2020

Thank you very much!