Find index of closing bracket for a given opening bracket in an expression

Last Updated : 13 Jan, 2023

Given a string with brackets. If the start index of the open bracket is given, find the index of the closing bracket. Examples:

Input : string = [ABC[23]][89]
        index = 0
Output : 8
The opening bracket at index 0 corresponds
to closing bracket at index 8.

The idea is to use Stack data structure. We traverse given expression from given index and keep pushing starting brackets. Whenever we encounter a closing bracket, we pop a starting bracket. If stack becomes empty at any moment, we return that index.

C++

// CPP program to find index of closing
// bracket for given opening bracket.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find index of closing
// bracket for given opening bracket.
void test(string expression, int index){
    int i;
     
    // If index given is invalid and is 
    // not an opening bracket.
    if(expression[index]!='['){
        cout << expression << ", " <<
                    index << ": -1\n";
        return;
    }
     
    // Stack to store opening brackets.
    stack <int> st;
     
    // Traverse through string starting from
    // given index.
    for(i = index; i < expression.length(); i++){
         
        // If current character is an 
        // opening bracket push it in stack.
        if(expression[i] == '[')
          st.push(expression[i]);
         
        // If current character is a closing
        // bracket, pop from stack. If stack 
        // is empty, then this closing
        // bracket is required bracket.
        else if(expression[i] == ']'){
            st.pop();
            if(st.empty()){
                cout << expression << ", " << 
                       index << ": " << i << "\n";
                return;
            }
        }
    }
     
    // If no matching closing bracket
    // is found.
    cout << expression << ", " <<
                index << ": -1\n";
}
 
// Driver Code
int main() {
    test("[ABC[23]][89]", 0); // should be 8
    test("[ABC[23]][89]", 4); // should be 7
    test("[ABC[23]][89]", 9); // should be 12
    test("[ABC[23]][89]", 1); // No matching bracket
    return 0;
}
 
// This code is contributed by Nikhil Jindal.

Java

// Java program to find index of closing 
// bracket for given opening bracket. 
import java.util.Stack;
class GFG {
 
// Function to find index of closing 
// bracket for given opening bracket. 
    static void test(String expression, int index) {
        int i;
 
        // If index given is invalid and is 
        // not an opening bracket. 
        if (expression.charAt(index) != '[') {
            System.out.print(expression + ", "
                    + index + ": -1\n");
            return;
        }
 
        // Stack to store opening brackets. 
        Stack<Integer> st = new Stack<>();
 
        // Traverse through string starting from 
        // given index. 
        for (i = index; i < expression.length(); i++) {
 
            // If current character is an 
            // opening bracket push it in stack. 
            if (expression.charAt(i) == '[') {
                st.push((int) expression.charAt(i));
            } // If current character is a closing 
            // bracket, pop from stack. If stack 
            // is empty, then this closing 
            // bracket is required bracket. 
            else if (expression.charAt(i) == ']') {
                st.pop();
                if (st.empty()) {
                    System.out.print(expression + ", "
                            + index + ": " + i + "\n");
                    return;
                }
            }
        }
 
        // If no matching closing bracket 
        // is found. 
        System.out.print(expression + ", "
                + index + ": -1\n");
    }
 
// Driver Code 
    public static void main(String[] args) {
        test("[ABC[23]][89]", 0); // should be 8 
        test("[ABC[23]][89]", 4); // should be 7 
        test("[ABC[23]][89]", 9); // should be 12 
        test("[ABC[23]][89]", 1); // No matching bracket 
    }
// this code is contributed by Rajput-Ji
}

Python

# Python program to find index of closing
# bracket for a given opening bracket.
from collections import deque
 
def getIndex(s, i):
 
    # If input is invalid.
    if s[i] != '[':
        return -1
 
    # Create a deque to use it as a stack.
    d = deque()
 
    # Traverse through all elements
    # starting from i.
    for k in range(i, len(s)):
 
        # Pop a starting bracket
        # for every closing bracket
        if s[k] == ']':
            d.popleft()
 
        # Push all starting brackets
        elif s[k] == '[':
            d.append(s[i])
 
        # If deque becomes empty
        if not d:
            return k
 
    return -1
 
# Driver code to test above method.
def test(s, i):
    matching_index = getIndex(s, i)
    print(s + ", " + str(i) + ": " + str(matching_index))
 
def main():
    test("[ABC[23]][89]", 0) # should be 8
    test("[ABC[23]][89]", 4) # should be 7
    test("[ABC[23]][89]", 9) # should be 12
    test("[ABC[23]][89]", 1) # No matching bracket
 
if __name__ == "__main__":
    main()

C#

// C# program to find index of closing 
// bracket for given opening bracket. 
using System;
using System.Collections;
public class GFG { 
 
// Function to find index of closing 
// bracket for given opening bracket. 
    static void test(String expression, int index) { 
        int i; 
 
        // If index given is invalid and is 
        // not an opening bracket. 
        if (expression[index] != '[') { 
            Console.Write(expression + ", "
                    + index + ": -1\n"); 
            return; 
        } 
 
        // Stack to store opening brackets. 
        Stack st = new Stack(); 
 
        // Traverse through string starting from 
        // given index. 
        for (i = index; i < expression.Length; i++) { 
 
            // If current character is an 
            // opening bracket push it in stack. 
            if (expression[i] == '[') { 
                st.Push((int) expression[i]); 
            } // If current character is a closing 
            // bracket, pop from stack. If stack 
            // is empty, then this closing 
            // bracket is required bracket. 
            else if (expression[i] == ']') { 
                st.Pop(); 
                if (st.Count==0) { 
                    Console.Write(expression + ", "
                            + index + ": " + i + "\n"); 
                    return; 
                } 
            } 
        } 
 
        // If no matching closing bracket 
        // is found. 
        Console.Write(expression + ", "
                + index + ": -1\n"); 
    } 
 
// Driver Code 
    public static void Main() { 
        test("[ABC[23]][89]", 0); // should be 8 
        test("[ABC[23]][89]", 4); // should be 7 
        test("[ABC[23]][89]", 9); // should be 12 
        test("[ABC[23]][89]", 1); // No matching bracket 
    } 
} 
 
// This code is contributed by 29AjayKumar

Javascript

// Javascript program to find index of closing
  // bracket for given opening bracket.
  class Stack {
    constructor() {
      this.items = [];
    }
 
    // add element to the stack
    push(element) {
      return this.items.push(element);
    }
 
    // remove element from the stack
    pop() {
      if (this.items.length > 0) {
        return this.items.pop();
      }
    }
 
    // view the last element
    top() {
      return this.items[this.items.length - 1];
    }
 
    // check if the stack is empty
    isEmpty() {
      return this.items.length == 0;
    }
 
    // the size of the stack
    size() {
      return this.items.length;
    }
 
    // empty the stack
    clear() {
      this.items = [];
    }
  }
 
  // Function to find index of closing
  // bracket for given opening bracket.
  function test(expression, index) {
    var i;
 
    // If index given is invalid and is
    // not an opening bracket.
    if (expression[index] != "[") {
      console.log(expression + ", " + index + ": -1");
      return;
    }
 
    // Stack to store opening brackets.
    let st = new Stack();
    //stack <int> st;
 
    // Traverse through string starting from
    // given index.
    for (i = index; i < expression.length; i++) {
      // If current character is an
      // opening bracket push it in stack.
      if (expression[i] == "[") st.push(expression[i]);
      // If current character is a closing
      // bracket, pop from stack. If stack
      // is empty, then this closing
      // bracket is required bracket.
      else if (expression[i] == "]") {
        st.pop();
        if (st.isEmpty()) {
          console.log(expression + ", " + index + ": " + i);
          return;
        }
      }
    }
 
    // If no matching closing bracket
    // is found.
    console.log(expression + ", " + index + ": -1");
  }
 
  // Driver Code
 
  test("[ABC[23]][89]", 0); // should be 8
  test("[ABC[23]][89]", 4); // should be 7
  test("[ABC[23]][89]", 9); // should be 12
  test("[ABC[23]][89]", 1); // No matching bracket
 
  // This code is contributed by satwiksuman

Output:

[ABC[23]][89], 0: 8
[ABC[23]][89], 4: 7
[ABC[23]][89], 9: 12
[ABC[23]][89], 1: -1

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

Suggest improvement

Find maximum of minimum for every window size in a given array

Find maximum difference between nearest left and right smaller elements

Share your thoughts in the comments

Stack implementation in different language

Some questions related to Stack implementation

Easy problems on Stack

Intermediate problems on Stack

Hard problems on Stack