题目描述

在命令格式定义字符串中，关键词（令牌）通过空格分隔，并有以下结构化标记：

• 大括号 { … } 表示“必选分支”，内部是若干以 | 分隔的分支，必须选择其中之一；
• 中括号 [ … ] 表示“可选分支”，内部内容可选出现；
• 分支内部又可嵌套任意深度的混合结构。

我们需要统计在任意合法命令中，每个必选关键词至少需要出现的次数。必选关键词指：无论如何选择可选分支或必选分支，都必须出现的那些关键词；其出现次数取每种最小分支组合下的最低值，再取所有分支的最大值（因为分支二选一，需对每条分支计算，然后取最小，再对并列大括号分组累加）。

本题为2025年9月3日华为机考原题

华为机考的介绍点击这里

题目内容

在 $IP$ 领域中对设备的操作是通过配置命令行实现，在设备的产品文档中会为该设备支持的每个命令定义格式。命令格式定义必须遵循格式定义的规范要求，规范要求如下表所示。

备注说明：

1.关键字、分组括号、分支选择符之间通过一个空格隔开。除了括号和分支选择符 $|$ 外，其他都视为关键字

2.命令行最长 $1000$ 个字符长度。

下面是一些正确命令格式定义示例：

1.d r { k | n k }
2.d r [ { k | n k } ]
3.d k { k | r { k m | n k } [ k r ] }

假设产品文档中的命令格式定义都经过确认是正确的，并且关键字、分支符、括号之间都已经用空格隔开了。现在需要统计某个定义中每个必选关键字至少需要出现的次数。

输入描述

输入字符串为一个命令的格式定义，命令格式定义都经过确认是正确的，并且关键字、分支符，括号之间都已经用空格隔开了。暂不需要考虑错误格式比如这种 $d\ k\ r$ { $a | d$} 。

输出描述

输出为两行，第一行为必选关键字，按单词字母顺序排序，并用一个空格隔开，第二行为对应第一行位置上必选关键字的最小出现次数，也是用一个空格隔开。

样例1

输入

d r { k | n k }

输出

d k r
1 1 1

说明

大括号分组{}表示必选，分组里面有 $2$ 个分支，每个分支都有 $k$ ，因此 $k$ 是必须输入的，并且次数为 $1$ 。

样例2

输入

d r [ { k | n k } ]

输出

d r
1 1

说明

后面的中括号是分组[]表示可选，因此里面的所有内容都可以不输入。

样例3

输入

d k { k | r { k m | n k } [ k r ] }

输出

d k
1 2

说明

后面的大括号分组{}表示必选，其中有 $2$ 个分支，递归分析每个分支中都必须输入至少 $1$ 个关键字 $k$ 。因此整个表达式要输入的 $k$ 的数量至少为 $2$ 。

样例4

输入

d r { m | n }

输出

d r
1 1

说明

虽然，{$m$|$n$} 表示 $m$ 和 $n$ 二选一，合法命令可以输入 $d$ $r$ $m$ 或者 $d$ $r$ $n$ 。

所以必选关键就只有 $d$ 和 $r$ 。

必选关键字的意思是：要满足格式定义，正确命令中必须出现的关键字。

样例5

输入

k { { b | { m | [ m | c | n ] | { c x s | a h d | w } } { h [ c h b | s h d | v ] { a | s c a | d } | { x g n | u | f } | c { s | a | h h e | e } { s c | u v m | w x u } | x { x | i | r } [ m | r h | g w ] } | [ { n w | b | n c a | b f } [ a b | e g c | u u | b w h ] { b g | u v | b b | k u x } | b { u k | x w s | b | x } [ i k | w s ] | [ d | k e ] ] | { { v b | e k n } { k g | r w m | a } [ k | r w ] | s [ a k m | x h ] | { n m | i | r u s } x h | [ r s | r s k | s c | i s ] [ f e | k | v ] } n a } [ { [ r a f | d g b | f ] | { b r | a a } | { x d a | n | f h c | r c } | { w | r } [ f e e | k m n | g ] } h { [ k | m | x f r | b k ] { s | h n x | s e } [ e g | h k s ] | [ r | e e c | h ] { w a | w s a | n } | [ w h | h | i b f ] k | [ r | c e i ] } | [ { k c b | b | r a f | i } | [ r k | n | u g g ] [ u u x | w v r | b m f | a s ] [ x | v a ] | { u f u | d m e | b e m } | { s i x | d | b s | g u } { a | i | v m | i } ] g [ x { d | a k a | c w v | e m b } | { r | c m | g k } c | { n m s | a | k | n } ] ] d | s { [ v | f { r v g | m | r w h | m m e } | [ k | x c x | g g ] [ a | n | k | a s r ] e ] [ { m | n | m r } [ u m u | x ] | { n | h i g | r e h } [ b r b | b r | h c s | w m ] s | u ] k | [ n c | [ u s m | k x | c a ] | { b | d a | s n n | g } [ w c | s i ] d ] { e | [ g g r | k u | v a h ] { d | i c | r r r | v } a } { [ e | b f e | e d ] | { s | r n | u m v } | [ x m d | x f | i e i | a n ] } | { [ g d | d | h s e | m n ] | [ i a f | c r ] [ d e g | f f h ] { r | g } } h } | g { { v | [ r m | k | w u ] { n a h | w e s } n } [ [ g e b | s | s i u | a ] [ f s d | g | v s h ] | { m m a | r w g | m b r | i b s } | [ w | w x d | w u g ] w ] | { n { b n n | c | s } | b b b } n | g } x | { [ { h | c v | c } [ f | d u x | n i | m d h ] { d m | u } | x ] { [ r b c | k | n | h m f ] | [ a v w | e r x | m c | g ] [ w | d | k | r v k ] } k | v [ { d e | a w } [ f g | a ] [ m n | i f ] | h [ i f | h a r ] ] { { b f | n r } | w r | { d c v | v k | a e | v } [ i k | f | h b v ] b | [ d g n | w m | v ] [ i c | h ] } } { { { k s k | v | v m } [ k i m | k i | x u n ] { n u x | c u g } | b r } x [ d { k | a e | n u a | k n } w | { x v w | g } { h | f | h h c } [ u | a k | x e u | s ] | { w b x | i m | c } f | { k f r | k g c } [ i b e | x i | m a | f ] v ] | n | [ { x d a | h | u m } [ s | m g | w ] | { d a m | f u | v n d | g } | d f [ u | b | s ] ] g } { a | { [ a | v | d | h c m ] [ d c | v ] | { i b a | h } | m x { e k h | a g c | c } | c g } } }

输出

k
1