Play With Brackets

Concepts Used

Stack

Difficulty Level

Easy.

Problem Statement :

Rashid is given a set of open and closed brackets of each type such as [ , ], ( , ) and { , } by his teacher and he is asked to construct a valid set of brackets from the given set. A set is said to be valid if

>1.Open brackets must be closed by the same type of closing brackets.
>
>2.Open brackets must be closed in the correct order.
You have to determine that the set constructed by Rashid is valid or not.

See original problem statement here

Example:

Input
3
{([])}
()
([]

Output
Valid
Valid
Not Valid

In the first and second test case each opening bracket 
is closed by the corresponding same type of closing bracket.

In the third test case, there is no closing bracket of '(', 
so the string is not valid.

EXPLANATION:

Using stack:

When any open symbol i.e, (, {, [ is encountered, it will be pushed in the stack.

If any close symbol i.e, ), }, ] is encountered, any of the three can happen

The TOS (Top Of Stack) is checked in data structures and algorithms, if the encountered close symbol matches with its open symbol, then open symbol which is at TOS is popped out.(OR)

The TOS (Top Of Stack) is checked, if the encountered close symbol does not match with its open symbol, then -1 is returned as there is no matching symbol. (OR)

The TOS (Top Of Stack) is checked,if the stack is empty, then -1 is returned as there is no open symbol in the stack.

SOLUTIONS:

[TABS_R id=2311]
[forminator_quiz id=”2312″]

Previous post Stack Challenge
Next post REVERSE LINK LIST

Leave a Reply

Your email address will not be published. Required fields are marked *