思路
我们先理解一下题目的意思:
正则表达式
+ x:表示一个字符
+ |:表示两边取哪边都行,我们这里为了使得可以接收的字符串最大,直接取字符串更多的那边
+ ():没有什么特殊含义,只是规定了计算的优先级
可以画一棵递归树辅助理解
代码
思路说的不是很明白,可以直接对着代码注释理解
#include<iostream>
#include<cstring>
using namespace std;
string str;
int k; //全局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往下移动,字符数量增加
res++;
k++;
}
}
return res;
}
int main()
{
cin>>str;
cout<<dfs();
return 0;
}
对右括号,左括号那里跳过的理解:
当碰到左括号时,先在本层跳过左括号,递归到下一层去处理(处理括号内的符号串),下一层一直处理完所有括号内的字符,碰到了右括号,因为是直接break,所以其实是在下一层碰到右括号直接不处理,退出,返回上一层,再直接把右括号给跳过了。如果我们在代码碰到右括号处再k++
跳过右括号,实际上会跳两次!
写的很好