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 [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

---