PTA 括号匹配 递归写法 测试用例均不通过

测试积点老人

1. import java.io.*;
   
2. import java.util.HashMap;
   
3. import java.util.Map;
   
4. 
   
5. public class Main {
   
6. 
   
7.     private static Map<Character,Character> map;
   
8.     //找到最远端的右括号并返回它的索引 c是右括号
   
9.     //如果没有找到返回-1
   
10.     public static int judge(String str,char c){
    
11.         for(int i=str.length()-1;i>0;i--){
    
12.             if(str.charAt(i)==c){
    
13.                 return i;
    
14.             }
    
15.         }
    
16.         return -1;
    
17.     }
    
18. 
    
19.     //递归方法 判断每一层嵌套是否合法 c是右括号
    
20.     //出口:内层无嵌套/达到最内层
    
21.     public static boolean ValidNest(String str,char c){
    
22.         //先找出右括号在局部字符串的最远端索引
    
23.         int cIndex = judge(str,c);
    
24.         //没找到，说明缺了右括号，错的
    
25.         if(cIndex==-1){
    
26.             return false;
    
27.         }
    
28.         //出口 下一个就是右括号了 说明这个左括号内部无嵌套 合法
    
29.         else if(cIndex==1){
    
30.             //如果右括号索引已经是子串结尾，为出口
    
31.             if(cIndex==str.length()-1){
    
32.                 return true;
    
33.             }
    
34.             //如果不是子串结尾，说明右方还有平行嵌套
    
35.             else{
    
36.                 cIndex++;
    
37.                 boolean leftFlag;
    
38.                 boolean rightFlag;
    
39.                 //需要递归判断的子串 这里直接截取到尾部
    
40.                 String subString = str.substring(cIndex);
    
41.                 //左子串的左括号
    
42.                 char leftBracket = map.get(subString.charAt(0));
    
43.                 //右子串的左括号 不知道有没有右子串 先放着
    
44.                 char rightBracket;
    
45.                 //找到左括号在子串中的右括号
    
46.                 int leftIndex = judge(subString,leftBracket);
    
47.                 //如果右括号索引不为尾索引，说明有平行嵌套
    
48.                 if(leftIndex!=subString.length()-1){
    
49.                     String leftString = subString.substring(0,leftIndex+1);
    
50.                     leftFlag = ValidNest(leftString,leftBracket);
    
51.                     rightBracket = map.get(subString.charAt(leftIndex+1));
    
52.                     //右子串从左子串右括号的下一个字符到子串尾部
    
53.                     String rightString = subString.substring(leftIndex+1);
    
54.                     rightFlag = ValidNest(rightString,rightBracket);
    
55.                     return leftFlag&&rightFlag;
    
56.                 }
    
57.                 else{
    
58.                     return ValidNest(subString,leftBracket);
    
59.                 }
    
60.             }
    
61.         }
    
62.         else{
    
63.             //这种情况下，说明右边还有，先递归判断左边嵌套，再递归判断右边嵌套，均正确则返回true
    
64.             boolean leftFlag;
    
65.             boolean rightFlag;
    
66.             //需要递归判断的子串
    
67.             String subString = str.substring(1,cIndex);
    
68.             //左子串的左括号
    
69.             char leftBracket;
    
70.             try{
    
71.                 leftBracket = map.get(subString.charAt(0));
    
72.             }
    
73.             catch (Exception e){
    
74.                 return false;
    
75.             }
    
76.             //右子串的左括号 不知道有没有右子串 先放着
    
77.             char rightBracket;
    
78.             //找到左括号在子串中的右括号
    
79.             int leftIndex = judge(subString,leftBracket);
    
80.             //如果右括号索引不为尾索引，说明有平行嵌套
    
81.             if(leftIndex!=subString.length()-1){
    
82.                 String leftString = subString.substring(0,leftIndex+1);
    
83.                 leftFlag = ValidNest(leftString,leftBracket);
    
84.                 rightBracket = map.get(subString.charAt(leftIndex+1));
    
85.                 //右子串从左子串右括号的下一个字符到子串尾部
    
86.                 String rightString = subString.substring(leftIndex+1);
    
87.                 rightFlag = ValidNest(rightString,rightBracket);
    
88.                 return leftFlag&&rightFlag;
    
89.             }
    
90.             else{
    
91.                 return ValidNest(subString,leftBracket);
    
92.             }
    
93.         }
    
94.     }
    
95. 
    
96.     public static void main(String[] args) throws IOException {
    
97.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
98.         StreamTokenizer st = new StreamTokenizer(br);
    
99. 
    
100.         st.nextToken();
     
101.         int total = (int)st.nval;
     
102. 
     
103.         map = new HashMap<>();
     
104.         map.put('{','}'); map.put('[',']'); map.put('(',')');
     
105. 
     
106.         for(int i=1;i<=total;i++){
     
107.             String brackets = br.readLine();
     
108.             char temp = map.get(brackets.charAt(0));
     
109.             boolean result=ValidNest(brackets,temp);
     
110.             if(result){
     
111.                 System.out.println("Yes");
     
112.             }
     
113.             else{
     
114.                 System.out.println("No");
     
115.             }
     
116.         }
     
117.     }
     
118. }
     

复制代码

思路： 递归判断每一层嵌套 每一层嵌套中可能有互相平行的括号，再分别进行递归判断，细节写在注释里了
现在发现一个测试用例是有问题的，为 {}({[]}())。因为在找第一个{的最远端的右括号时找到了后面嵌套里的}。
请问有没有什么改正的方法？
注：请不要贴一个AC代码的链接上来。

qqq911

按顺序找?

bellas

等大神

海海豚

https://www.csdn.net/tags/MtTagg5sMDA0ODQtYmxvZwO0O0OO0O0O.html 参考这个试试

jingzizx

栈的应用