lyh20021209
2022-05-13 10:20
采纳率: 76.9%
浏览 27
已结题

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

img

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

img


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

1条回答 默认 最新

相关推荐 更多相似问题