正则语法

本题设计到的语法规则不多

• .：只匹配一个任意字符，本题中用x代替

• ()：只匹配和括号里内容相同的字符串
  比如(abc)可以匹配123abc123，但是不能匹配123ab123（注意中间少了c）

• |：匹配带有其左边部分或右边部分的字符串
  比如a|b可以匹配带有a或b的字符串，而a|b|c可以匹配a、b、c，也可以用.，但一般不这么做

• 可以嵌套和搭配使用
  如(a|b)123可以匹配a123和b123，但不能匹配ab123

#include <iostream>
#include <algorithm>
using namespace std;

char s[110];

// u-开始处理的位置，d-当前递归层数
int dfs(int u, int d)
{
    // deep != d，说明该部分字符串已经被递归处理过
    int cnt = 0, deep = d;
    for(int i = u; s[i]; i++)
    {
        if(s[i] == 'x')
        {
            if(deep == d)
                cnt++;
        }
        else if(s[i] == '|')
        {
            if(deep != d)
                continue;
            cnt = max(cnt, dfs(i + 1, d));
            // 因为即使有多个|（如x|x|x），也只会和下一个x比较，所以可以直接结束
            break;
        }
        else if(s[i] == '(')
        {
            if(deep == d)
                cnt += dfs(i + 1, d + 1);
            deep++;
        }
        else if(s[i] == ')')
        {
            deep--;
            // 每次递归只需要处理括号内的字符串
            if(deep < d)
                break;
        }
    }
    return cnt;
}

int main()
{
    cin >> s;
    cout << dfs(0, 0);
}