AcWing4865. 有效类型

原题链接：原题链接

代码思路参考大佬题解：大佬题解转接口

在本题中，关于有效类型字符串，具体定义如下：

• int是有效类型字符串。
• 如果字符串 X和字符串 Y都是有效类型字符串，则 pair<X,Y>是有效类型字符串。

现有一行若干个单词，每个单词要么是 pair，要么是 int，并且其中 int的数量恰好为

n

n

n
个。

你可以在不改变单词顺序的前提下，在这一行中任意添加 <、>、,符号。

你的任务是构造出一个有效类型字符串。

输出这个有效类型字符串。

注意：

1. 有效类型字符串中不含空格或其它多余字符。
2. 可以证明如果存在满足条件的有效类型字符串，那么它一定是唯一的。
3. 如果不存在满足条件的有效类型字符串，输出 Error occurred即可。

输入格式
第一行包含整数

n

n

n，表示给定单词中 int的数量。

第二行包含若干个单词，每个单词要么是 pair，要么是 int。

输出格式
输出满足条件的有效类型字符串，如果不存在，则输出 Error occurred。

注意，有效类型字符串中不含空格或其它多余字符。

数据范围
前

6

6

6个测试点满足：

1

≤

n

≤

5

1 \le n \le 5

1≤n≤5。
所有测试点满足：

1

≤

n

≤

1

0

5

1≤n≤10^{5}

1≤n≤105，输入的总单词数量不超过

1

0

5

10^{5}

105，输入的 int数量恰好为

n

n

n。

思路

按照pair合理的排列方式可以看出来，一个合理的代码串一定是pair套pair然后套int，所以可以采用递归的方式来进行判断，具体看代码。
判负则是看末尾，如果已经到末尾了递归还没结束则是负，或者是递归结束但还有单词在继续输入则也是负。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

string s, str;
int flag = 1;

void input()
{
    if (cin >> s )
    {
        str += s;
        if ( s == "pair" )
        {
            str += '<';
            input();
            str += ',';
            input();
            str += '>';
        }
    }
    else flag = 0;
}

void solve()
{
    int n;
    cin >> n;
    input();
    if (cin >> s) flag = 0;
    if (!flag) cout << "Error occurred\n";
    else cout << str << '\n';
}

int main()
{
    int T = 1;
    while (T -- )
    {
        solve();
    }
    return 0;
}