Valid Parentheses
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

Question

Valid Parentheses

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

Accepted Answer

Valid Parenthesis

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.

Space Complexity: O(n)Explanation:

O(N), Where N is the length of the string.

As the maximum stack size reaches the length of the string.

Time Complexity: O(n)Explanation:

O(N), Where N is the length of the string.

As the traversal of the string or expression is done only once.

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

Input Format:

Output format :

Note:

Constraints:

Top ExpertLancing Research Services Software Engineer interview questions & answers

Popular interview questions of Software Engineer