题目描述
在命令格式定义字符串中，关键词（令牌）通过空格分隔，并有以下结构化标记：
- 大括号
{ … } 表示“必选分支”，内部是若干以 | 分隔的分支，必须选择其中之一；
- 中括号
[ … ] 表示“可选分支”，内部内容可选出现；
- 分支内部又可嵌套任意深度的混合结构。
我们需要统计在任意合法命令中，每个必选关键词至少需要出现的次数。必选关键词指：无论如何选择可选分支或必选分支，都必须出现的那些关键词；其出现次数取每种最小分支组合下的最低值，再取所有分支的最大值（因为分支二选一，需对每条分支计算，然后取最小，再对并列大括号分组累加）。
P3556.第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
输入
n { h { a i n | n [ v ] } | s i {m | k | m n } n | r i { { n | a } | m n } | g n | u n [ d n ] } { b { c | m n } } { c { d [ e ] f { c [ d ] { c { f { d e { a { b n } } } [ d ] } } } } } [ b ] n { h { b i n | n [ v ] } | s i { m | k | w w } n | r i { n | m n } | g n | u n [ d n ] | u { n | a } [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { e { f { d [ d ] { e { f { d e { a { b n } } } [ d ] } } } } } { h { b i { n | a } | n [ v ] } | s i { m | k | w w } n | r i { n | m n } | g n | u n | [ d n ] | u n [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { n { f { a { a { b n } } } [ d ] } } } } } [ x ] { n | a } { h { a i n | n [ v ] } | r i { n | m n } | g n | u n [ d n ] | u n [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { e { f { d e { b { b n } } } [ d ] } } } } } [ k ] { n | a } { h { a i n | n [ v ] } | s i { m | k | w w} n | r i { n | m n } | g { n | a } | u { n | a } [ d n ] | u n [ d n ] } { n | [ d ] n } { [ a b ] | [ b n ] }
输出
n
2
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
