1597. 正则问题

涉及到括号的都可以使用递归处理,每发现一层括号,就递归进入下一层,单独处理这个括号内的所有内容。直到最细的一层没有括号为止。

所以对于每一层递归可以:

  • 读到 x ,令当前计次变量自增
  • 读到 | ,用当前计次变量更新当前层最值,然后置零计次变量重新计次
  • 读到 ( ,进入下一层,当前计次变量赋值为递归结果
  • 读到 ) ,退出当前层,返回当前层最值
  • 读到其他字符 (不管是 EOF 还是什么),说明输入完了,直接返回

可以在每次递归读入输入,也可以每次递归读入全局已读好的字符串。

具体实现参考代码:

#include <bits/stdc++.h> using namespace std; int finished; int dfs() { char x; int now = 0, maxv = 0; while ((x = getchar()) != EOF && !finished) { if (x == 'x') ++now; else if (x == '(') now += dfs(); else if (x == ')') break; else if (x == '|') maxv = max(maxv, now), now = 0; else { finished = true; break; } } return max(maxv, now); } int main() { printf("%d", dfs()); return 0; }