1225. 正则问题(递归)

本文主要是介绍1225. 正则问题(递归)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1225. 正则问题

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

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

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

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

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

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

数据范围
输入长度不超过100，保证合法。

输入样例：
((xx|xxx)x|(x|xx))xx
输出样例：
6
题解
X 表示字符
| 表示左右两边都可以，选择一个
递归就是树
对应成一颗树。

s = input().strip()
k = 0def dfs():global kres = 0while k < len(s):if s[k] == '(':k += 1res += dfs()k += 1elif s[k] == '|':k += 1res = max(dfs(), res)elif s[k] == ')':breakelif s[k] == 'x':res += 1k += 1return res
print(dfs())

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int k;
string str;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 ++ ;  // 跳过 'x'res ++ ;}}return res;
}int main()
{cin >> str;cout << dfs() << endl;return 0;
}

这篇关于1225. 正则问题(递归)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---