Valid Parentheses

Posted: 13 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

Input Format:
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only line of input of each test case contains a string, as described in the task.
Output format :
For each test case, the first and the only line of output prints whether the string or expression is balanced or not.

The output of every test case is printed in a separate line.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5

Where N is the length of the input string or expression.

Time Limit: 1 sec
Approach 1

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 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 is balanced else it is not balanced.

 

Pseudo Code:

  • Declare a character stack.
  • Now traverse the expression string

       1-  If the current character is a starting bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to 

     stack .

       2-  If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from 

     stack and if the popped character is the matching starting bracket then fine 

     else parenthesis are not balanced.

  • After complete traversal, if there is some starting bracket left in the stack then “not balanced”.
  • Otherwise, the string is balanced.
Try Problem