原题链接：正则问题

题目描述

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入格式

一个由x()|组成的正则表达式。

输出格式

输出所给正则表达式能接受的最长字符串的长度。

数据范围

输入长度不超过100，保证合法。

输入样例1：

((xx|xxx)x|(x|xx))xx 

输出样例1：

6

思路

有一说一，递归真是艺术

学到了一种分析方法：画树

对于这道题，可以画一个递归树

以此为例子
((xx|xxx)x|(x|xx))xx 

那么如果根据这个来写递归呢

其实，括号里面就是一层递归，遇到左括号就下一层，遇到 ‘|’ 也忘下一层递归，当然，要记得跳过 (，)，|

时间复杂度

$O(n)$

C++ 代码

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

string str;
int k;

int dfs() {

    int res = 0;
    while(k < str.size()) {
        if(str[k] == '(') { // 处理 (.....)
            k ++;   // 跳过左括号
            res += dfs();
            k ++;   // 跳过右括号
        }else if(str[k] == '|') {
            k ++;   // 跳过 '|'
            res = max(res,dfs());
        }else if(str[k] == ')') break;
        else {
            k ++;
            res ++;
        }
    }
    return res;
}

int main()
{
    cin >> str;
    cout << dfs() << endl;
    return 0;
}