Find Index of Closing Bracket for a Given Opening Bracket in an Expression

Problem Statement

Given a string s of length/size n and an integer value representing the index of an opening square bracket. Find index of closing bracket for a given opening bracket in an expression.

Example

s = "[ABC[23]][89]"

index = 0

8

s = "[C-[D]]"

index = 3

5

s = "E-[FX]]"

index = 0

-1

Approach

Use a stack data structure of integer type to store the index of the opening brackets in the given string. Start iterating through the given string starting from the given index. If an opening bracket is encountered push it in the stack. For every closing bracket that is encountered pop an opening bracket from the stack. If the stack becomes empty i.e. the size of the stack is 0 at some index, print the index. Else print -1.

Algorithm

1. Initialize a string s of length/size n and an integer value representing the index of an opening square bracket.
2. Create the function to find an index of the closing bracket for the given opening bracket in the given string which accepts a string value representing expression and an integer value representing the index of an opening bracket in the given string as it’s a parameter.
3. Check if the character at given index is not equal to an opening bracket i.e. ‘[‘, print -1, and return.
4. After that create a stack data structure of integer type to store the index of opening brackets of the given string in it.
5. Traverse through the given string starting from the given index and check if the character at the current index in the string is equal to an opening bracket, push/insert the character at the current index in the string in the stack.
6. Else if the character at the current index in the string is equal to a closing bracket i.e. ‘]’, pop/remove the element at the top of the stack. After that, check if the stack is empty i.e. size of the stack is equal to 0, print the current index and return.
7. Print -1.

Code

C++ Program to find corresponding closing bracket for opening bracket

#include <bits/stdc++.h> 
using namespace std; 
  
void test(string expression, int index){ 
    int i; 
      
    if(expression[index]!='['){ 
        cout << "-1\n"; 
        return; 
    } 
      
    stack <int> st; 
      
    for(i = index; i < expression.length(); i++){ 
          
        if(expression[i] == '['){ 
            st.push(expression[i]);
        }
          
        else if(expression[i] == ']'){ 
            st.pop(); 
            if(st.empty()){ 
                cout << i << "\n"; 
                return; 
            } 
        } 
    } 
      
    cout << "-1\n"; 
} 
  
int main() { 
    string s = "[ABC[23]][89]";
    int index = 0;
    
    test(s, index); 
    
    return 0; 
}

8

Java Program to find corresponding closing bracket for opening bracket

import java.util.Stack; 

class FindIndex{ 
  
    static void test(String expression, int index){ 
        int i; 
  
        if(expression.charAt(index) != '['){ 
            System.out.print("-1\n"); 
            return; 
        } 
  
        Stack<Integer> st = new Stack<>(); 
  
        for(i = index; i < expression.length(); i++){ 
  
            if(expression.charAt(i) == '['){ 
                st.push((int) expression.charAt(i)); 
            } 
            
            else if(expression.charAt(i) == ']'){ 
                st.pop(); 
                if(st.empty()){ 
                    System.out.print( i ); 
                    return; 
                } 
            } 
        } 
  
        System.out.print("-1\n"); 
    } 
  
    public static void main(String[] args){
        String s = "[ABC[23]][89]";
        int index = 0;
        
        test(s, index); 
    } 
}

8

Complexity Analysis

Time Complexity

O(n) where n is the length of the given string s. Since we have traversed over all the characters available in the string, the time complexity is linear.

Space Complexity

O(n) because we used space to store the characters of the given string. The space complexity is dependent on the number of brackets. But in worst-case, all the characters might be square brackets. Thus the space complexity is also linear.

References