PTA 括号匹配 递归写法 测试用例均不通过
import java.io.*;
import java.util.HashMap;
import java.util.Map;
public class Main {
private static Map<Character,Character> map;
//找到最远端的右括号并返回它的索引 c是右括号
//如果没有找到返回-1
public static int judge(String str,char c){
for(int i=str.length()-1;i>0;i--){
if(str.charAt(i)==c){
return i;
}
}
return -1;
}
//递归方法 判断每一层嵌套是否合法 c是右括号
//出口:内层无嵌套/达到最内层
public static boolean ValidNest(String str,char c){
//先找出右括号在局部字符串的最远端索引
int cIndex = judge(str,c);
//没找到，说明缺了右括号，错的
if(cIndex==-1){
return false;
}
//出口 下一个就是右括号了 说明这个左括号内部无嵌套 合法
else if(cIndex==1){
//如果右括号索引已经是子串结尾，为出口
if(cIndex==str.length()-1){
return true;
}
//如果不是子串结尾，说明右方还有平行嵌套
else{
cIndex++;
boolean leftFlag;
boolean rightFlag;
//需要递归判断的子串 这里直接截取到尾部
String subString = str.substring(cIndex);
//左子串的左括号
char leftBracket = map.get(subString.charAt(0));
//右子串的左括号 不知道有没有右子串 先放着
char rightBracket;
//找到左括号在子串中的右括号
int leftIndex = judge(subString,leftBracket);
//如果右括号索引不为尾索引，说明有平行嵌套
if(leftIndex!=subString.length()-1){
String leftString = subString.substring(0,leftIndex+1);
leftFlag = ValidNest(leftString,leftBracket);
rightBracket = map.get(subString.charAt(leftIndex+1));
//右子串从左子串右括号的下一个字符到子串尾部
String rightString = subString.substring(leftIndex+1);
rightFlag = ValidNest(rightString,rightBracket);
return leftFlag&&rightFlag;
}
else{
return ValidNest(subString,leftBracket);
}
}
}
else{
//这种情况下，说明右边还有，先递归判断左边嵌套，再递归判断右边嵌套，均正确则返回true
boolean leftFlag;
boolean rightFlag;
//需要递归判断的子串
String subString = str.substring(1,cIndex);
//左子串的左括号
char leftBracket;
try{
leftBracket = map.get(subString.charAt(0));
}
catch (Exception e){
return false;
}
//右子串的左括号 不知道有没有右子串 先放着
char rightBracket;
//找到左括号在子串中的右括号
int leftIndex = judge(subString,leftBracket);
//如果右括号索引不为尾索引，说明有平行嵌套
if(leftIndex!=subString.length()-1){
String leftString = subString.substring(0,leftIndex+1);
leftFlag = ValidNest(leftString,leftBracket);
rightBracket = map.get(subString.charAt(leftIndex+1));
//右子串从左子串右括号的下一个字符到子串尾部
String rightString = subString.substring(leftIndex+1);
rightFlag = ValidNest(rightString,rightBracket);
return leftFlag&&rightFlag;
}
else{
return ValidNest(subString,leftBracket);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(br);
st.nextToken();
int total = (int)st.nval;
map = new HashMap<>();
map.put('{','}'); map.put('[',']'); map.put('(',')');
for(int i=1;i<=total;i++){
String brackets = br.readLine();
char temp = map.get(brackets.charAt(0));
boolean result=ValidNest(brackets,temp);
if(result){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
}
思路： 递归判断每一层嵌套 每一层嵌套中可能有互相平行的括号，再分别进行递归判断，细节写在注释里了
现在发现一个测试用例是有问题的，为 {}({[]}())。因为在找第一个{的最远端的右括号时找到了后面嵌套里的}。
请问有没有什么改正的方法？
注：请不要贴一个AC代码的链接上来。
按顺序找? 等大神 https://www.csdn.net/tags/MtTagg5sMDA0ODQtYmxvZwO0O0OO0O0O.html 参考这个试试 栈的应用
页:
[1]
