Check for balanced parentheses in an expression.
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

Check for balanced parentheses in an expression.

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

A stack can be used to solve this question.
We traverse the given string s and if we:
1. see open bracket we put it to stack
2. see closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.

Complexity: Time complexity is O(n): we put and pop each element of string from our stack only once. Space complexity is O(n).

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 Snapdeal Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Snapdeal Software Engineer