# Print bracket number

Print bracket number problem: In this article, we are going to see a problem that has been featured in Flipkart interview.
Submitted by Radib Kar, on March 31, 2019 [Last updated : March 20, 2023]

## Problem Description

Given an expression exp of length n consisting of some brackets. The task is to print the bracket numbers when the expression is being parsed.

## Example

```    Input expression:
(a+b)/(c+d)

Output:
1 1 2 2

Input expression:
((()()(())))

Output:
1 2 3 3 4 4 5 6 6 5 2 1
```

## Solution of Print bracket number

So we actually need to parse the entire expression and whenever we are receiving an opening bracket we need to memorize its occurrence. So, we need a stack actually.

Pre-requisite:

String s – which is to be parsed

### Algorithm

```1.  Declare a stack st and a vector a;
2.  Set count1; //for the first opening bracket
3.  FOR i=0: length of string s
IF s[i]=='(' //opening bracket
Append count to a;
Push count to stack st
Increment count;
ELSE IF s[i]==')' //closing bracket
Pop from stack and append to a
ELSE //for other characters
Do nothing
4.  Print vector a;
```

### Example with explanation

```    Input example 1:
(a+b)/(c+d)

Iteration 0:
i=0
s[i]='('
count=1
append 1 to a
vector status:
1
push 1 to stack st
stack status :
1
increment count
count=2
-----------------------------------------

Iteration 1:
i=1
s[i]='a'
do nothing
vector status:
1
stack status :
1
-----------------------------------------

Iteration 2:
i=2
s[i]='+'
do nothing
vector status:
1
stack status :
1
-----------------------------------------

Iteration 3:
i=3
s[i]='b'
do nothing
vector status:
1
stack status :
1
-----------------------------------------

Iteration 4:
i=4
s[i]=')'
pop from stack and push to a
vector status:
1 , 1
stack status :
empty
-----------------------------------------

Iteration 5:
i=5
s[i]='/'
do nothing
vector status:
1, 1
stack status :
empty
-----------------------------------------

Iteration 6:
i=6
s[i]='('
count=2
append 2 to a
vector status:
1, 1, 2
push 2 to stack st
stack status :
2
increment count
count=3
-----------------------------------------

Iteration 7:
i=7
s[i]='c'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------

Iteration 8:
i=8
s[i]='+'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------

Iteration 9:
i=9
s[i]='d'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------

Iteration 10:
i=10
s[i]=')'
pop from stack and push to a
vector status:
1 , 1, 2, 2
stack status :
empty

Iteration ends as end of string is reached
```

### C++ implementation of Print bracket number

```#include <bits/stdc++.h>
using namespace std;

void print(vector<int> a)
{
for (int i = 0; i < a.size(); i++)
cout << a[i] << " ";
cout << endl;
}

void my(string s)
{
stack<int> st;
vector<int> a;
int count = 1;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') { //opening bracket
a.push_back(count);
st.push(count++);
}
else if (s[i] == ')') { //closing bracket
a.push_back(st.top());
st.pop();
}
}
print(a);
}

int main()
{
int t, n, item;
string s;

cout << "Enter expression\n";
cin >> s;

cout << "Printing bracket no sequence...\n";
my(s);

return 0;
}
```

### Output

```First run:
Enter expression
(a+b)/(c+d)
Printing bracket no sequence...
1 1 2 2

Second run:
Enter expression
((()(())))
Printing bracket no sequence...
1 2 3 3 4 5 5 4 2 1
```