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++
#include <bits/stdc++.h>
using namespace std;
void test(string expression, int index){
int i;
if (expression[index]!= '[' ){
cout << expression << ", " <<
index << ": -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 << expression << ", " <<
index << ": " << i << "\n" ;
return ;
}
}
}
cout << expression << ", " <<
index << ": -1\n" ;
}
int main() {
test( "[ABC[23]][89]" , 0);
test( "[ABC[23]][89]" , 4);
test( "[ABC[23]][89]" , 9);
test( "[ABC[23]][89]" , 1);
return 0;
}
|
Java
import java.util.Stack;
class GFG {
static void test(String expression, int index) {
int i;
if (expression.charAt(index) != '[' ) {
System.out.print(expression + ", "
+ index + ": -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(expression + ", "
+ index + ": " + i + "\n" );
return ;
}
}
}
System.out.print(expression + ", "
+ index + ": -1\n" );
}
public static void main(String[] args) {
test( "[ABC[23]][89]" , 0 );
test( "[ABC[23]][89]" , 4 );
test( "[ABC[23]][89]" , 9 );
test( "[ABC[23]][89]" , 1 );
}
}
|
Python
from collections import deque
def getIndex(s, i):
if s[i] ! = '[' :
return - 1
d = deque()
for k in range (i, len (s)):
if s[k] = = ']' :
d.popleft()
elif s[k] = = '[' :
d.append(s[i])
if not d:
return k
return - 1
def test(s, i):
matching_index = getIndex(s, i)
print (s + ", " + str (i) + ": " + str (matching_index))
def main():
test( "[ABC[23]][89]" , 0 )
test( "[ABC[23]][89]" , 4 )
test( "[ABC[23]][89]" , 9 )
test( "[ABC[23]][89]" , 1 )
if __name__ = = "__main__" :
main()
|
C#
using System;
using System.Collections;
public class GFG {
static void test(String expression, int index) {
int i;
if (expression[index] != '[' ) {
Console.Write(expression + ", "
+ index + ": -1\n" );
return ;
}
Stack st = new Stack();
for (i = index; i < expression.Length; i++) {
if (expression[i] == '[' ) {
st.Push(( int ) expression[i]);
}
else if (expression[i] == ']' ) {
st.Pop();
if (st.Count==0) {
Console.Write(expression + ", "
+ index + ": " + i + "\n" );
return ;
}
}
}
Console.Write(expression + ", "
+ index + ": -1\n" );
}
public static void Main() {
test( "[ABC[23]][89]" , 0);
test( "[ABC[23]][89]" , 4);
test( "[ABC[23]][89]" , 9);
test( "[ABC[23]][89]" , 1);
}
}
|
Javascript
class Stack {
constructor() {
this .items = [];
}
push(element) {
return this .items.push(element);
}
pop() {
if ( this .items.length > 0) {
return this .items.pop();
}
}
top() {
return this .items[ this .items.length - 1];
}
isEmpty() {
return this .items.length == 0;
}
size() {
return this .items.length;
}
clear() {
this .items = [];
}
}
function test(expression, index) {
var i;
if (expression[index] != "[" ) {
console.log(expression + ", " + index + ": -1" );
return ;
}
let st = new Stack();
for (i = index; i < expression.length; i++) {
if (expression[i] == "[" ) st.push(expression[i]);
else if (expression[i] == "]" ) {
st.pop();
if (st.isEmpty()) {
console.log(expression + ", " + index + ": " + i);
return ;
}
}
}
console.log(expression + ", " + index + ": -1" );
}
test( "[ABC[23]][89]" , 0);
test( "[ABC[23]][89]" , 4);
test( "[ABC[23]][89]" , 9);
test( "[ABC[23]][89]" , 1);
|
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)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!