给定一个带括号的字符串。如果给出了开放括号的开始索引，则找到封闭括号的索引。
null
例如：
Input : string = [ABC[23]][89]
index = 0
Output : 8
The opening bracket at index 0 corresponds
to closing bracket at index 8.
这个想法是使用 堆栈数据结构 .我们从给定的索引遍历给定的表达式，并不断推起始括号。每当我们遇到一个结束括号，我们就会弹出一个开始括号。如果堆栈随时变为空，我们将返回该索引。
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" ; 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 << "" ; return ; } } } // If no matching closing bracket // is found. cout << expression << ", " << index << ": -1" ; } // 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" ); 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 + "" ); return ; } } } // If no matching closing bracket // is found. System.out.print(expression + ", " + index + ": -1" ); } // 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" ); 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 + "" ); return ; } } } // If no matching closing bracket // is found. Console.Write(expression + ", " + index + ": -1" ); } // 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 |
输出：
[ABC[23]][89], 0: 8 [ABC[23]][89], 4: 7 [ABC[23]][89], 9: 12 [ABC[23]][89], 1: -1
时间复杂性： O（n） 辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
