侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-26 / 0 评论 / 0 点赞 / 183 阅读 / 897 字
温馨提示:
本文最后更新于 2023-02-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4865. 有效类型 - AcWing题库


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

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

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

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

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

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

注意:

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

输入格式

第一行包含整数 nn ,表示给定单词中 int 的数量。

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

输出格式

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

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

数据范围

66 个测试点满足: 1n51 \le n \le 5
所有测试点满足: 1n1051 \le n \le 10^5 ,输入的总单词数量不超过 10510^5 ,输入的 int 数量恰好为 nn

输入样例1:

3
pair pair int int int

输出样例1:

pair<pair<int,int>,int>

输入样例2:

1
pair int

输出样例2:

Error occurred

解题

方法一:递归

思路

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

image-20230226085558547

那么本题的要求就变成了:输入一串节点序列,判断该序列是否是且仅是合法的一棵二叉树的前序遍历形式,如果是,将其前序遍历拼上 '<'',''>' 后输出,否则输出 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");
    }
}
0

评论区