给定两个括号序列S1和S2，由“（’和’）”组成。任务是检查通过连接两个序列获得的字符串是否平衡。连接可以通过s1+s2或s2+s1完成。
null
例如：
输入： s1=“）（）（（））”，s2=“（（）（（））” 输出： 平衡的 s2+s1=“（（）（（）））”，其中 是一个平衡的括号序列。
输入： s1=“（（））（”，s2=“（））（）” 输出： 不平衡 s1+s2=“（（））（（））（（））”–>不平衡 s2+s1=“（））（））（（））（“–>不平衡
A. 缺乏经验的 解决方案是首先连接两个序列，然后使用堆栈检查结果序列是否平衡。首先，检查s1+s2是否平衡。如果不平衡，则检查s2+s1是否平衡。要检查给定的括号序列是否平衡，或者是否使用堆栈，可以使用以下算法。
- 声明一个字符堆栈S。
- 现在遍历表达式字符串exp。
- 如果当前字符是起始括号（“（”或“{”或“[”），则将其推入堆栈。
- 如果当前字符是右括号（“）”或“}”或“]”），则从堆栈中弹出，如果弹出的字符是匹配的起始括号，则右括号不平衡。
- 完成遍历后，如果堆栈中还剩下一些起始括号，则“不平衡”。
以下是上述方法的实施情况：
C++
// CPP program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. #include <bits/stdc++.h> using namespace std; // Check if given string is balanced bracket // sequence or not. bool isBalanced(string s) { stack< char > st; int n = s.length(); for ( int i = 0; i < n; i++) { // If current bracket is an opening // bracket push it to stack. if (s[i] == '(' ) st.push(s[i]); // If current bracket is a closing // bracket then pop from stack if // it is not empty. If stack is empty // then sequence is not balanced. else { if (st.empty()) { return false ; } else st.pop(); } } // If stack is not empty, then sequence // is not balanced. if (!st.empty()) return false ; return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. bool isBalancedSeq(string s1, string s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) return true ; // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code. int main() { string s1 = ")()(())))" ; string s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) cout << "Balanced" ; else cout << "Not Balanced" ; return 0; } |
JAVA
// Java program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. import java.util.Stack; class GFG { // Check if given string is balanced bracket // sequence or not. static boolean isBalanced(String s) { Stack<Character> st = new Stack<Character>(); int n = s.length(); for ( int i = 0 ; i < n; i++) { // If current bracket is an opening // bracket push it to stack. if (s.charAt(i) == '(' ) { st.push(s.charAt(i)); } // If current bracket is a closing // bracket then pop from stack if // it is not empty. If stack is empty // then sequence is not balanced. else if (st.empty()) { return false ; } else { st.pop(); } } // If stack is not empty, then sequence // is not balanced. if (!st.empty()) { return false ; } return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. static boolean isBalancedSeq(String s1, String s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) { return true ; } // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code. public static void main(String[] args) { String s1 = ")()(())))" ; String s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) { System.out.println( "Balanced" ); } else { System.out.println( "Not Balanced" ); } } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to check if sequence obtained # by concatenating two bracket sequences # is balanced or not. # Check if given string is balanced bracket # sequence or not. def isBalanced(s): st = list () n = len (s) for i in range (n): # If current bracket is an opening # bracket push it to stack. if s[i] = = '(' : st.append(s[i]) # If current bracket is a closing # bracket then pop from stack if # it is not empty. If stack is empty # then sequence is not balanced. else : if len (st) = = 0 : return False else : st.pop() # If stack is not empty, then sequence # is not balanced. if len (st) > 0 : return False return True # Function to check if string obtained by # concatenating two bracket sequences is # balanced or not. def isBalancedSeq(s1, s2): # Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)): return True # Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1) # Driver Code if __name__ = = "__main__" : s1 = ")()(())))" s2 = "(()(()(" if isBalancedSeq(s1, s2): print ( "Balanced" ) else : print ( "Not Balanced" ) # This code is contributed by # sanjeev2552 |
C#
// C# program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. using System; using System.Collections.Generic; class GFG { // Check if given string is balanced bracket // sequence or not. static bool isBalanced(String s) { Stack< char > st = new Stack< char >(); int n = s.Length; for ( int i = 0; i < n; i++) { // If current bracket is an opening // bracket push it to stack. if (s[i] == '(' ) { st.Push(s[i]); } // If current bracket is a closing // bracket then pop from stack if // it is not empty. If stack is empty // then sequence is not balanced. else if (st.Count==0) { return false ; } else { st.Pop(); } } // If stack is not empty, then sequence // is not balanced. if (st.Count!=0) { return false ; } return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. static bool isBalancedSeq(String s1, String s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) { return true ; } // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code. public static void Main(String[] args) { String s1 = ")()(())))" ; String s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) { Console.WriteLine( "Balanced" ); } else { Console.WriteLine( "Not Balanced" ); } } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to check if sequence // obtained by concatenating two bracket // sequences is balanced or not. // Check if given string is balanced // bracket sequence or not. function isBalanced(s) { let st = []; let n = s.length; for (let i = 0; i < n; i++) { // If current bracket is an opening // bracket push it to stack. if (s[i] == '(' ) { st.push(s[i]); } // If current bracket is a closing // bracket then pop from stack if // it is not empty. If stack is empty // then sequence is not balanced. else if (st.length == 0) { return false ; } else { st.pop(); } } // If stack is not empty, then sequence // is not balanced. if (st.length != 0) { return false ; } return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. function isBalancedSeq(s1, s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) { return true ; } // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code let s1 = ")()(())))" ; let s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) { document.write( "Balanced" ); } else { document.write( "Not Balanced" ); } // This code is contributed by mukesh07 </script> |
输出：
Balanced
时间复杂性： O（n） 辅助空间： O（n）
一 有效率的 解决方案是检查给定序列是否可以在不使用堆栈的情况下生成平衡括号序列，即在恒定的额外空间中。 设串联序列为s。有两种可能性：s=s1+s2平衡或s=s2+s1平衡。检查这两种可能性s是否平衡。
- 如果s是平衡的，则在穿过s的任何时刻，s中的开口括号的数量应始终大于或等于s中的闭合括号的数量。这是因为，如果在任何时刻，s中结束括号的数量大于开始括号的数量，那么最后一个结束括号将不会在s中有匹配的开始括号（这就是计数更多的原因）。
- 如果序列是平衡的，那么在遍历结束时，s中的开口括号的数量等于s中的闭合括号的数量。
以下是上述方法的实施情况：
C++
// C++ program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. #include <bits/stdc++.h> using namespace std; // Check if given string is balanced bracket // sequence or not. bool isBalanced(string s) { // To store result of comparison of // count of opening brackets and // closing brackets. int cnt = 0; int n = s.length(); for ( int i = 0; i < n; i++) { // If current bracket is an // opening bracket, then // increment count. if (s[i] == '(' ) cnt++; // If current bracket is a // closing bracket, then // decrement count and check // if count is negative. else { cnt--; if (cnt < 0) return false ; } } // If count is positive then // some opening brackets are // not balanced. if (cnt > 0) return false ; return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. bool isBalancedSeq(string s1, string s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) return true ; // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code. int main() { string s1 = ")()(())))" ; string s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) cout << "Balanced" ; else cout << "Not Balanced" ; return 0; } |
JAVA
// Java program to check if // sequence obtained by // concatenating two bracket // sequences is balanced or not. import java.io.*; class GFG { // Check if given string // is balanced bracket // sequence or not. static boolean isBalanced(String s) { // To store result of comparison // of count of opening brackets // and closing brackets. int cnt = 0 ; int n = s.length(); for ( int i = 0 ; i < n; i++) { // If current bracket is // an opening bracket, // then increment count. if (s.charAt(i) == '(' ) { cnt = cnt + 1 ; } // If current bracket is a // closing bracket, then // decrement count and check // if count is negative. else { cnt = cnt - 1 ; if (cnt < 0 ) return false ; } } // If count is positive then // some opening brackets are // not balanced. if (cnt > 0 ) return false ; return true ; } // Function to check if string // obtained by concatenating // two bracket sequences is // balanced or not. static boolean isBalancedSeq(String s1, String s2) { // Check if s1 + s2 is // balanced or not. if (isBalanced(s1 + s2)) return true ; // Check if s2 + s1 is // balanced or not. return isBalanced(s2 + s1); } // Driver code public static void main(String [] args) { String s1 = ")()(())))" ; String s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) { System.out.println( "Balanced" ); } else { System.out.println( "Not Balanced" ); } } } // This code is contributed // by Shivi_Aggarwal |
Python3
# Python3 program to check # if sequence obtained by # concatenating two bracket # sequences is balanced or not. # Check if given string # is balanced bracket # sequence or not. def isBalanced(s): # To store result of # comparison of count # of opening brackets # and closing brackets. cnt = 0 n = len (s) for i in range ( 0 , n): if (s[i] = = '(' ): cnt = cnt + 1 else : cnt = cnt - 1 if (cnt < 0 ): return False if (cnt > 0 ): return False return True def isBalancedSeq(s1, s2): if (isBalanced(s1 + s2)): return True return isBalanced(s2 + s1) # Driver code a = ")()(())))" ; b = "(()(()(" ; if (isBalancedSeq(a, b)): print ( "Balanced" ) else : print ( "Not Balanced" ) # This code is contributed # by Shivi_Aggarwal |
C#
// C# program to check if // sequence obtained by // concatenating two bracket // sequences is balanced or not. using System; class GFG { // Check if given string // is balanced bracket // sequence or not. static bool isBalanced(String s) { // To store result of comparison // of count of opening brackets // and closing brackets. int cnt = 0; int n = s.Length; for ( int i = 0; i < n; i++) { // If current bracket is // an opening bracket, // then increment count. if (s[i] == '(' ) { cnt = cnt + 1; } // If current bracket is a // closing bracket, then // decrement count and check // if count is negative. else { cnt = cnt - 1; if (cnt < 0) return false ; } } // If count is positive then // some opening brackets are // not balanced. if (cnt > 0) return false ; return true ; } // Function to check if string // obtained by concatenating // two bracket sequences is // balanced or not. static bool isBalancedSeq(String s1, String s2) { // Check if s1 + s2 is // balanced or not. if (isBalanced(s1 + s2)) return true ; // Check if s2 + s1 is // balanced or not. return isBalanced(s2 + s1); } // Driver code public static void Main() { String s1 = ")()(())))" ; String s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) { Console.WriteLine( "Balanced" ); } else { Console.WriteLine( "Not Balanced" ); } } } // This code is contributed by // PrinciRaj1992 |
PHP
<?php // PHP program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. // Check if given string is balanced bracket // sequence or not. function isBalanced( $s ) { // To store result of comparison of // count of opening brackets and // closing brackets. $cnt = 0; $n = strlen ( $s ); for ( $i = 0; $i < $n ; $i ++) { // If current bracket is an // opening bracket, then // increment count. if ( $s [ $i ] == '(' ) $cnt ++; // If current bracket is a // closing bracket, then // decrement count and check // if count is negative. else { $cnt --; if ( $cnt < 0) return false; } } // If count is positive then // some opening brackets are // not balanced. if ( $cnt > 0) return false; return true; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. function isBalancedSeq( $s1 , $s2 ) { // Check if s1 + s2 is balanced or not. if (isBalanced( $s1 + $s2 )) return true; // Check if s2 + s1 is balanced or not. return isBalanced( $s2 + $s1 ); } // Driver code. $s1 = ")()(())))" ; $s2 = "(()(()(" ; if (!isBalancedSeq( $s1 , $s2 )) echo "Balanced" ; else echo "Not Balanced" ; // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript program to check if sequence obtained // by concatenating two bracket sequences // is balanced or not. // Check if given string is balanced bracket // sequence or not. function isBalanced(s) { // To store result of comparison of // count of opening brackets and // closing brackets. var cnt = 0; var n = s.length; for ( var i = 0; i < n; i++) { // If current bracket is an // opening bracket, then // increment count. if (s[i] == '(' ) cnt++; // If current bracket is a // closing bracket, then // decrement count and check // if count is negative. else { cnt--; if (cnt < 0) return false ; } } // If count is positive then // some opening brackets are // not balanced. if (cnt > 0) return false ; return true ; } // Function to check if string obtained by // concatenating two bracket sequences is // balanced or not. function isBalancedSeq(s1, s2) { // Check if s1 + s2 is balanced or not. if (isBalanced(s1 + s2)) return true ; // Check if s2 + s1 is balanced or not. return isBalanced(s2 + s1); } // Driver code. var s1 = ")()(())))" ; var s2 = "(()(()(" ; if (isBalancedSeq(s1, s2)) document.write( "Balanced" ); else document.write( "Not Balanced" ); </script> |
输出：
Balanced
时间复杂性： O（n） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
