# 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

Problem statement:

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:

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:

```#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
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates