括号匹配方案

野性酷女 2022-06-08 08:38 42阅读 0赞

合法的括号匹配序列被定义为：  
1、空串“”是合法的括号序列  
2、如果“x”和“y”是合法的序列，那么“xy”也是合法的序列  
3、如果“x”是合法的序列，那么“（x）”也是合法的序列  
4、每个合法的括号序列都可以由上面的规则生成  
东东现在有一个合法的括号序列s，一次移除操作分为两步：  
1、移除序列s中第一个左括号  
2、移除序列s中任意一个右括号。保证操作之后s还是一个合法的括号序列  
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空。如果两个方案中有一次移除操作中移除的是不同的右括号就认为是不同的方案  
输入描述：输入包括一行，一个合法的括号序列s，序列长度length（2<=length<=20）  
输出描述：输出一个整数，表示方案数  
import java.util.\*;  
public class Main \{

private static int total = 0;
    /**
     * 判断括号序列是否合法
     * @return
     */
    public static Boolean volid(ArrayList<Character> list){
        Stack<Character> s = new Stack<>();
        for(int i = 0; i < list.size(); i++){
            if(list.get(i) == '('){
                s.push('(');
            }else{
                if(s.isEmpty() || s.pop() != '(') return false; 
            }
        }
        return s.isEmpty();
    }
    
    public static void dfs(ArrayList<Character> list){
        if(list.isEmpty()){
            total++;
            return ;
        }
        ArrayList<Character> newList = null;
        Character lft = list.remove(0);
        for(int i = 0; i < list.size(); i++){
            if(list.get(i) == ')'){
                newList = (ArrayList)list.clone();
                //删除右括号后判断该序列是否合法，如果合法递归，否则检查下一个右括号
                newList.remove(i);
                if(volid(newList)){
                    dfs(newList);
                }
            }
        }
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        ArrayList<Character> list = new ArrayList<>();
        while(in.hasNext()){
            list.clear();
            String line = in.nextLine();
            char[] s = line.toCharArray();
            for(int i = 0; i < line.length(); i++){
                list.add(s[i]);
            }
            total = 0;
            dfs(list);
            System.out.println(total);
        }
    }