Dada una string con corchetes. Si se proporciona el índice de inicio del paréntesis abierto, busque el índice del paréntesis de cierre.
Ejemplos:
Input : string = [ABC[23]][89]
index = 0
Output : 8
The opening bracket at index 0 corresponds
to closing bracket at index 8.
La idea es utilizar la estructura de datos Stack . Atravesamos la expresión dada desde el índice dado y seguimos empujando los paréntesis iniciales. Cada vez que encontramos un paréntesis de cierre, sacamos un paréntesis de inicio. Si la pila se vacía en cualquier momento, devolvemos ese índice.
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
Producción:
[ABC[23]][89], 0: 8 [ABC[23]][89], 4: 7 [ABC[23]][89], 9: 12 [ABC[23]][89], 1: -1
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Rahul Chawla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA