nowcoder-括号匹配问题

题目来源：

https://www.nowcoder.com/practice/380380e6c6b444888ae145593ccbbbca?tpId=90&tqId=30840&tPage=4&rp=4&ru=/ta/2018test&qru=/ta/2018test/question-ranking

题目描述：

合法的括号匹配序列被定义为:

空串””是合法的括号序列
如果”X”和”Y”是合法的序列,那么”XY”也是一个合法的括号序列
如果”X”是一个合法的序列,那么”(X)”也是一个合法的括号序列
每个合法的括号序列都可以由上面的规则生成
例如””, “()”, “()()()”, “(()())”, “(((())))”都是合法的。东东现在有一个合法的括号序列s,一次移除

操作分为两步:

移除序列s中第一个左括号
移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
例如: s = “()()()()()”,输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
s = “(((())))”,输出24, 第一次有4种情况, 第二次有3种情况, … ,依次类推, 4 * 3 * 2 * 1 = 24

思路：

反向遍历，用count记录”)“数量，用res记录结果，每次遍历到”)“则count加一，遍历到”(“则结果乘以count，表示该”(“可以匹配的”)”选择为count数，之后count减一继续遍历，遍历完序列后的res即为方案数量。

参考代码：

public class Now_64 {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String input = bf.readLine();
        int len=input.length();
        int res=1;
        int count=0;
        for(int i=len-1;i>=0;i--){
            if(input.charAt(i)==')'){
                count++;
            }
            else {
                res*=count;
                count--;
            }
        }
        System.out.println(res);
    }
}