P8650 [蓝桥杯 2017 省 A] 正则问题

· · 题解

P8650 [蓝桥杯 2017 省 A] 正则问题

既然标签是递归，那就来一个递归的题解吧！

tips:本题解与其他题解代码相似，主要是思维解释。

AC Code:

省的你们翻得累死。

#include <bits/stdc++.h>
using namespace std;
int re(int ans){
    char c;
    while(cin>>c){
        if(c == '\r' || c == '\n') return ans;
        else if(c == 'x') ans ++;
       else if(c == '(') ans += re(0);
        else if(c == ')') return ans;
        else if(c == '|') return max(ans, re(0));
    }
    return ans;
} 
int main() {
    cout<<re(0);
    return 0;
}
//很短，对吧

解释

首先要有对递归的思路：

定义操作：re(int ans) 函数；

必要参数：int ans 用来记录当前的答案；

子操作：

循环输入字符，每输入一个字符就判断这个字符是什么?

  1. 是 x 则将 ans 增加；

  2. 是 ( 则进入递归，统计括号内的字符数，也就是 re(0)，同时将答案增加返回值；

  3. 是 ) 则将当前答案返回；

  4. 是 | 则计算当前的答案和接下来的答案的最大值，也就是 ans + f(0)。

边界：输入完了，退出。

补充一下 | 的芝士：

返回 | 左边和右边的答案的最大值，比如 xxxx|xxxxxxxxx 就会返回 9。