Print Bracket Number

Print Bracket Number” is a stack based basic problem asked in technical round of product- based company. Here, in this problem, we are given a expression string of balanced brackets and our task is to print the bracket number when the expression is being parsed.

Example:

Expression: (())()
Bracket Number: 1 2 2 1 3 3
 
Expression: ()()()
Bracket Number: 1 1 2 2 3 3 
 
Expression: (())()(())()
Bracket Number: 1 2 2 1 3 3 4 5 5 4 6 6

METHOD 1: Stack Based Solution

The steps to find and print the bracket number are as follows:

  1. Create an empty integer stack.
  2. Create a vector to store the bracket number as result and initialize a local variable, say, count with 0.
  3. Scan the expression string.
  4. If the character is open bracket ‘(‘, then push count into stack and vector both. Then increment count with 1.
  5. If the character is closing bracket ‘)’, then push top of stack into vector and pop out the stack.
  6. After the string is completely scanned, print the vector as result, which stores all the bracket numbers.

C++ Program to Find and Print Bracket Number is as follows:

/* C++ Program to Find Bracket Number */
#include<bits/stdc++.h>
using namespace std;

/* Function to Print Bracket Number */
void printBracketNumber(string str)
{
    /* Create an Empty Stack and a vector*/
    stack<int> st;
    vector<int> vc;
    
    int count = 1; /* A counter to store current bracket number */
    
    for(int i = 0; i < str.length();i++)
    {
        /* 
            If the character is open bracket, then push the count 
            into both vector and stack and then increment count with one
        */
        if(str[i] == '(')
        {
            vc.push_back(count);
            st.push(count);
            count++;
        }
        else
        {
            /*
                If the character is closing bracket, then push top of stack
                into vector and then pop out the stack
            */
            vc.push_back(st.top());
            st.pop();
        }
    }
    
    /* Printing the Bracket Number */
    cout<<"The Bracket Number for Given Expression is:\n";
    for(int i = 0; i < vc.size(); i++)
    cout<<vc[i]<<" ";
}
int main()
{
    string str = "(())()(()())";
    printBracketNumber(str);
}
OUTPUT:
The Bracket Number for Given Expression is:
1 2 2 1 3 3 4 5 5 6 6 4

Related Posts:

  1. Next Greater Frequency Element
  2. Sort a Stack using Temporary Stack
  3. Infix to Postfix Conversion
  4. Infix to Prefix Conversion
  5. Prefix to Infix Conversion
  6. Prefix to Postfix Conversion
  7. Postfix to Infix Conversion
  8. Postfix to Prefix Conversion
  9. Check whether given Parentheses String are Balanced Parentheses or Not.
  10. Next Greater Element
  11. Find Minimum number of bracket reversals required to make an expression balanced.
  12. Implement Queue Using Two Stacks.
  13. Merge Overlapping Intervals using Stacks
  14. Implement Stack Using Linked List
  15. Largest Rectangular Area in Histogram
  16. Length of Longest Valid Substring
  17. Reverse a String using Stack
  18. Implement two stacks in a single array
  19. Program to find most frequent element in an array.
  20. Program to find pair in an array with given sum.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *