Print Bracket Number - Coding

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.

Examples :

Input : (a+(b*c))+(d/e)
Output : 1 2 2 1 3 3
The highlighted brackets in the given expression
(a+(b*c))+(d/e) has been assigned the numbers as:
1 2 2 1 3 3.

Input : ((())(()))
Output : 1 2 3 3 2 4 5 5 4 1

Source: Flipkart Interview Experience | Set 49.

Approach :

Define a variable left_bnum = 1.
Create a stack right_bnum.
Now, for i = 0 to n-1.
1. If exp[i] == ‘(‘, then print left_bnum, push left_bnum on to the stack right_bnum and finally increment left_bnum by 1.
2. Else if exp[i] == ‘)’, then print the top element of the stack right_bnum and then pop the top element from the stack.

Implementation:

C++

<?php
// PHP implementation to 
// print the bracket number
 
// function to print
// the bracket number
function printBracketNumber($exp, $n)
{
    // used to print the 
    // bracket number for 
    // the left bracket
    $left_bnum = 1;
     
    // used to obtain the 
    // bracket number for 
    // the right bracket
    $right_bnum = array();
    $t = 0;
     
    // traverse the given
    // expression 'exp'
    for ($i = 0; $i < $n; $i++) 
    {
         
        // if current character 
        // is a left bracket
        if ($exp[$i] == '(')
        {
             
            // print 'left_bnum',
            echo $left_bnum . " ";
             
            // push 'left_bnum' on to
            // the stack 'right_bnum'
            $right_bnum[$t++] = $left_bnum;
             
            // increment 'left_bnum' by 1
            $left_bnum++;
        }
         
        // else if current character
        // is a right bracket
        else if($exp[$i] == ')') 
        {
 
            // print the top element 
            // of stack 'right_bnum'
            // it will be the right 
            // bracket number
            echo $right_bnum[$t - 1] . " ";
             
            // pop the top element
            // from the stack
            $right_bnum[$t - 1] = 1;
            $t--;
        }
    }
}
 
// Driver Code
$exp = "(a+(b*c))+(d/e)";
$n = strlen($exp);
 
printBracketNumber($exp, $n);
     
// This code is contributed 
// by mits
?>

Javascript

<script>
 
// Javascript implementation to print the bracket number
 
// function to print the bracket number
function printBracketNumber(exp, n)
{
    // used to print the bracket number
    // for the left bracket
    var left_bnum = 1;
     
    // used to obtain the bracket number 
    // for the right bracket
    var right_bnum = [];
     
    // traverse the given expression 'exp'
    for (var i = 0; i < n; i++) {
         
        // if current character is a left bracket
        if (exp[i] == '(') {
            // print 'left_bnum',
            document.write( left_bnum + " ");
             
            // push 'left_bnum' on to the stack 'right_bnum'
            right_bnum.push(left_bnum);
             
            // increment 'left_bnum' by 1
            left_bnum++;
        }
         
        // else if current character is a right bracket
        else if(exp[i] == ')') {
 
            // print the top element of stack 'right_bnum'
            // it will be the right bracket number
            document.write( right_bnum[right_bnum.length-1] + " ");
             
            // pop the top element from the stack
            right_bnum.pop();
        }
    }
}
 
// Driver program to test above
var exp = "(a+(b*c))+(d/e)";
var n = exp.length;
 
printBracketNumber(exp, n);
 
</script>

Output:

1 2 2 1 3 3

Time Complexity : O(n).
Auxiliary Space : O(n).

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Find value of (1^n + 2^n + 3^n + 4^n ) mod 5
Numbers having difference with digit sum more than s
Division without using '/' operator
Check if a given number is Pronic \| Efficient Approach
Power of a prime number ‘r’ in n!

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	7