Bracket Number

Posted: 7 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given a string ‘S’ comprising of some brackets. You need to print the number of every bracket.

For Example:
If S = (pq)() 
Then the output will be 1 1 2 2. First pair of opening and closing brackets will get the same number and so does the 2nd pair.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains a string ‘S’.
Output Format:
For each test case, print the number of every bracket separated by a space.

Output of each test case will be printed on a new line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= |S| <= 10^5

Where ‘|S|’ is the length of a particular string.

Time Limit: 1 Sec
Approach 1

Approach: The basic idea to solve this problem is to use a stack. We will maintain a stack ‘STACK’ and a variable ‘CNT’ which will keep the count number of brackets. When ‘(‘ is encountered we will increment the ‘CNT’ and push it in the ‘STACK’ and ‘RES’ vector. When ‘)’ is encountered we will pop the top element of the ‘STACK’ and push it in ‘RES’ vector.

 

Algorithm:

 

  1. Take a stack ‘STACK’ and a vector ‘RES’ to store the result.
  2. Initialize a variable ‘CNT’ to ‘0’.
  3. Traverse the string from ‘i’ equals 0 to ‘S.length’.
    • If S[i] equals ‘(‘.
      • Increment ‘CNT’
      • Push ‘CNT’ in STACK.
      • Push ‘CNT’ to ‘RES’
    • If S[i] equals ‘)’
      • Initialize ‘TEMP’ as ‘STACK.top( )’.
      • Pop top from ‘STACK’.
      • Push ‘TEMP’ to ‘RES’
  4. Return ‘RES’.
Try Problem