×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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




Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.