Home »
Interview coding problems/challenges
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
TOP Interview Coding Problems/Challenges