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