正则问题

作者: smatrcHendsa | 来源:发表于2019-03-18 08:34 被阅读0次

    经典的递归DFS 我对递归的理解不够深啊
    看到括号 应该很轻松的想到是经典的递归问题 然后只有四个符号()x| 分别判断 就行了 要考虑多个||||||中间不同的元素的处理

    问题描述
      考虑一种简单的正则表达式:
      只由 x ( ) | 组成的正则表达式。
      小明想求出这个正则表达式能接受的最长字符串的长度。

    例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是: xxxxxx,长度是6。
    输入格式
      一个由x()|组成的正则表达式。输入长度不超过100,保证合法。
    输出格式
      这个正则表达式能接受的最长字符串的长度。
    样例输入
    ((xx|xxx)x|(x|xx))xx
    样例输出
    6
    数据规模和约定
      峰值内存消耗(含虚拟机) < 256M
      CPU消耗 < 1000ms

    #include <stdio.h>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    string str;
    int si, crt;
    
    int dfs() {
        int cnt = 0, mx = 0;
        //sum是所有的加起来  cnt的单次的
        while (crt < si) {
            char c = str.at(crt);
            if (c == '(') {
                crt++;
                cnt += dfs();
            }
            else if (c == 'x') {
                cnt++;
                crt++;
                mx = max(mx, cnt);
            }
            else if (c == '|') {
                mx = max(mx, cnt);
                cnt = 0;
                crt++;
            }
            else {
                crt++;
                break;
            }
        }
        mx = max(mx, cnt);
        return mx;
    }
    int main() {
        cin >> str;
        si = str.size();
        cout << dfs() << endl;
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:正则问题

        本文链接:https://www.haomeiwen.com/subject/bboumqtx.html