**Introduction**

A string is one of the most popular data structures, probably equal to the array, and you will find at least one String question in any programming job interview.

Today we will solve one of the most famous questions on a string- “Balanced Parentheses.” frequently asked in Amazon.

Keep an eye out for the approach, as there will be plenty of hints to help you develop a solution ahead of time. Do try to solve it by yourself before moving on to the approach.

**Problem Statement of Balanced Parentheses**

**You’re given the string ‘STR’ consisting solely of “{“, “}”, “(“, “)”, “[“ and “]”. Determine whether the parentheses are balanced.**

**Sample Input :** 2 [()]{}{[()()]()} [(]) **Sample Output :** Balanced Not Balanced

Note: An input string is said to be balanced if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

We advise you to think about how you can solve this problem more thoroughly, champ.

Okay, let me give you some hints before we move on.

**Hint 1:**

A valid parenthesis expression has the interesting property that a sub-expression of a valid expression must also be a valid expression. (Not all sub-expression).

For example: Consider a string **{ [ [ ] { } ] } ( ) ( )**

**Hint 2:**

What if we simply remove the matching pair of parentheses whenever we come across them in the expression? It would further shorten the expression.

For example:

{ { ( { } ) } } //remove matching pair 1 |_| { { ( ) } } //remove matching pair 2 |______| { { } } //remove matching pair 3 |__________| { } |________________| Above all are VALID EXPRESSIONS!

**Hint 3:**

When a problem is represented in terms of one or more subproblems, the most used concept that comes to mind is Recursion.

We can’t really process this from the inside out because we don’t know what the overall structure looks like. The stack data structure can come in handy here in representing this recursive structure of the problem.

Without further ado, let’s move on to the actual approach.

Make use of the stack. Traverse the string and push the current character in the stack if it is an opening brace; else pop from the stack. If it is the corresponding starting brace for the current closing brace, then move to the next character of the string; otherwise, return false.

If after complete traversal, if the stack is empty, then the string has balanced parentheses. Else it is not balanced.