PTA 括号匹配递归写法测试用例均不通过 - 51Testing软件测试论坛

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");
}
}
}
}

复制代码