括號匹配問題

鏈接：https://ac.nowcoder.com/acm/contest/3530/E
來源：牛客網(wǎng)

眾所周知，佳爺是集訓(xùn)隊最強(qiáng)，他經(jīng)常喜歡鄙視集訓(xùn)隊最菜的PC，這天他又來了，他丟給PC一道題目：

給你一個字符串，該字符串只包含符號 ‘(’ 和 ‘)’, ，我們稱那些左右括號可以一一對應(yīng)的括號字符串為完美字符串，

比如"()()()", “((()))”, “((()))()()”, 都是完美字符串

而"((())", “()(”, “((()))()(” 不是完美字符串。

這么難的題目，PC當(dāng)然是不會寫的，但他又不想被佳爺鄙視，所以他找到了你，聰明的ACMer啊，請你幫PC解出這題把

輸入描述:

第一行一個整數(shù)n，代表字符串的長度 n， 1 <= n <= 1e5

第二行一串字符串s，只包含字符 ‘(’ , ‘)’。

輸出描述:

如果該字符串是完美字符串，就輸出YES，。否則輸出NO

示例1
輸入

4

(())

輸出

YES

import java.util.Scanner; import java.util.Stack;public class Main {//https://ac.nowcoder.com/acm/contest/3530/E//判斷給定的字符串是不是完美括號public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();String input=sc.next();//將字符串轉(zhuǎn)換為字符數(shù)組char []chars=input.toCharArray();//用棧來進(jìn)行匹配Stack<String> stack=new Stack<>();//i用來計數(shù)，如果for循環(huán)結(jié)束i的值和數(shù)組的長度相同，則YES，反之NOint i;for ( i=0;i<chars.length;i++){if (chars[i]=='(') {stack.push(chars[i] + "");}else{if (stack.empty()){break; }else{stack.pop();}}}if (i==chars.length&&stack.empty()){System.out.println("YES");}else {System.out.println("NO");}} }

總結(jié)：
1.應(yīng)用棧進(jìn)行匹配是最直接的，如果位左括號(，就入棧，如果為右括號)，就出棧，需要注意的是在右括號出棧的時候需要判斷棧是否為空，比如輸入序列為：）（），此時就需要注意了。
2.最后用if判斷輸出YES還是NO時候，需要判斷計數(shù)變量i的值是否等于字符數(shù)組的長度，還要判斷棧是否為空，因為可能存 （）（ 這種情況，也是需要注意的。

總結(jié)

以上是生活随笔為你收集整理的00004-括号匹配问题-牛客网-要考虑各种情况的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。