Print Bracket Number

by · June 29, 2020

“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. Check whether given Parentheses String are Balanced Parentheses or Not.
  4. Next Greater Element
  5. Find Minimum number of bracket reversals required to make an expression balanced.
  6. Implement Queue Using Two Stacks.
  7. Merge Overlapping Intervals using Stacks
  8. Implement Stack Using Linked List
  9. Largest Rectangular Area in Histogram
  10. Length of Longest Valid Substring
  11. Reverse a String using Stack
  12. Implement two stacks in a single array
  13. Find Most Frequent Character of the String.
  14. Check Anagram Strings.
  15. Check Whether Given String is Palindromic Anagram or Not.
  16. Check Whether Given String is Panagram or Not.
  17. Find First Non-Repeating Character of the String.
  18. Find Most Frequent Element of the Array.
  19. Find Pair in an Array with Given Sum.
  20. Find First Repeating Element of an Array.

Tags:

You may also like...