【二叉树, 递归】有效类型

题目

4865. 有效类型 - AcWing题库

---

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

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

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

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

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

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

注意：

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

输入格式

第一行包含整数 $n$ ，表示给定单词中 int 的数量。

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

输出格式

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

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

数据范围

前 $6$ 个测试点满足： $1 \le n \le 5$ 。
所有测试点满足： $1 \le n \le 10^5$ ，输入的总单词数量不超过 $10^5$ ，输入的 int 数量恰好为 $n$ 。

输入样例1：

3
pair pair int int int

输出样例1：

pair<pair<int,int>,int>

输入样例2：

1
pair int

输出样例2：

Error occurred

解题

方法一：递归

思路

在本题中，有效类型字符串是递归定义的，可以把整个有效类型字符串看成一棵二叉树：其中 pair 节点必定有两个子节点，而 int 节点必定没有节点，例如：

那么本题的要求就变成了：输入一串节点序列，判断该序列是否是且仅是合法的一棵二叉树的前序遍历形式，如果是，将其前序遍历拼上 '<' 、 ',' 、 '>' 后输出，否则输出 Error occurred 。

具体做法是：（本题中给出的 n 没用）

• 递归处理序列输入：
  • 如果遇到 pair 就递归处理左右子树。
  • 如果遇到 int 就说明没有左右子节点了，直接回溯即可。
• 在递归过程中，如果输入到了文件尾，那么序列一定不合法（因为本应该有子节点的地方没有节点以供使用了）。
• 在递归完成后，如果输入还没结束，说明序列肯定不止一棵数，那也是不合法的。

代码

import java.util.*;
import java.io.*;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static String s;
    static StringBuilder ans = new StringBuilder();
    
    static boolean dfs() throws IOException {
        if (in.nextToken() == in.TT_EOF) return false;
        s = in.sval;
        if (s.equals("pair")) {
            ans.append("pair<");
            if (!dfs()) return false;
            ans.append(',');
            if (!dfs()) return false;
            ans.append('>');
        } else ans.append("int");
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        System.out.println(dfs() && in.nextToken() == in.TT_EOF ? ans : "Error occurred");
    }
}