Balanced Parentheses

Problem Statement

Given an input expression string of length n consisting of three types of parentheses - {,},(,),[,].Check for balanced parentheses in the expression (well-formedness) using Stack. Parentheses are balanced if:

1. The same kind of parentheses are used to close any open ones.
2. The proper sequence must be used to close any open parentheses.

Example

1. Input: expression = ~([]){}[[(){}]{}] Output: Yes, Balanced
2. Input: expression = [(])) Output: No, Not Balanced
3. It’s real life application is during the compilation of any code

Example Explanation

1. As in example 1, there is every closing bracket according to their corresponding opening brackets so yes this is balanced parentheses.

2. In the second example, it is observable that the parentheses are not balanced because the ( at the 2nd position in the expression should be closed before the closing of the ].

3. In the 3rd example, there is no { for the } that is in line number 8 of the code. Due to this, an error will be raised if we will try to run the code.

Constraints

• $1<=n<=10^3$
• All of characters in the sequence ∈ (,),{,},[,].

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Approach

We must make an observation in order to resolve this problem. The most recent opening parenthesis must coincide with the subsequent closing symbol as you read symbols from left to right. Additionally, it's possible that the very last symbol processed will be the one to match the first opening symbol. Opening and closing symbols are matched from the inside out, in the opposite order from which they first appear. This is a hint that the issue can be resolved using stacks.

Algorithm

• Declare an empty stack.
• Now start traversing the input string.
  • If you come across an opening bracket while traversing the string, add it to the stack.
  • Else the current character is a closing bracket. In this case, check to see if the top element of the stack is of the corresponding opening type and if it is then pop the top element from the stack and if not, then return false.
• If the stack is empty after traversing the string, return true; otherwise, return false.

Code Implementation

In C++

In Java

In Python

Output

Time Complexity:

As we are traversing over the expression of length n only once using the for loop so O(n) will be it's time complexity.

Space Complexity:

As we are creating a new stack and the size of stack can grow upto the size of the input string which is n, so O(n) auxiliary space will be used.