正则问题（递归搜索树)

原题链接：1225. 正则问题 - AcWing题库

考虑一种简单的正则表达式 $x()|$ 只由三种元素组成，要找到该表达式锁能接受的最长字符串

思路

递归问题，很明显可以看到正则表达式中的计算是有优先级的， 不妨把最外面的运算称为最低级，括号内的运算高一级，正则表达式的计算过程可以看成括号内的计算先进行，结果再参与括号外的运算，要如何按照优先级做运算是解决问题的关键。

只是按照括号或 “或” 划分字符串后递归处理解决不了并列的运算，要让递归程序判断优先级，计算高层次后返回到低层次再继续运算，即遇到括号进一层递归，计算完括号的结果后返回上一层。 这样一来，或的运算就可以处理为同级的比较，但是 或 右边的终点在哪里？可以认为与当前 或 同级别的运算结束了，或 就结束了，因此 或 也用递归处理，但是遇到递归退出条件后直接退出，不做处理，因为 或 的退出是同级别运算，这一层次结束要到左括号的递归返回才算结束，所以在左括号处做处理

实现

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<char> s;
 
int idx;
 
int find_num()
{
    int ans = 0;
    while(idx < s.size())
    {
        if(s[idx] == '(')
        {
            idx ++;
            ans += find_num();
            
            //必须等括号结束了再加
            idx ++;
        }
        else if(s[idx] == ')')
        {
            //idx ++;  当读到）时，可以表示括号结束，也可以是或结束，
            //在括号里的或，结束了不能再加1，否则括号无法结束，括号结束后再加
            
            //高层次结束
            break;
        }
        else if(s[idx] == '|')
        {
            idx ++;
            //层级已经细分了。所以比较是同级比较
            ans = max(ans, find_num());
            //不在括号里的或，会读到结尾才返回，不需要加1
        }
        else 
        {
            idx ++;
            ans ++;
        }
    }
    
    return ans;
}
 
 
int main()
{
    char c;
    while(cin >> c) s.push_back(c);
    
    int ans = find_num();
    
    cout << ans << endl;
    
    return 0;
}