题目描述

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

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

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

思路概述

1. 解析表达式 将输入按空格切分为令牌列表，利用递归下降或栈结构，构建语法树节点，包括：

   • 普通关键词节点（Token）
   • 顺序节点（Sequence），表示一系列子节点依次出现
   • 分支节点（Branch），表示由大括号或中括号包裹的子节点，其中包含若干分支选项及“必选”或“可选”属性

2. 计算最小出现次数 对每个节点定义函数 $f(node)$，返回一个映射：每个关键词到最低出现次数。

   • Token：$f(关键词k)={k:1}$

   • Sequence：$f([n_1,\dots,n_m])$=${mergePlus}(f(n_1),\dots,f(n_m))$，即对应关键词相加出现次数，未出现视为 0。

   • Branch：

     • 若“必选”分支 $\{b_1|\dots|b_p\}$：对每个分支 $b_i$ 计算 $f(b_i)$，然后对每个关键词取“在所有分支中的最小值”，即 $f_{\min}(k)=\min_{1\le i\le p}f_{b_i}(k)\,.$
     • 若“可选”分支 $[b_1|\dots|b_p]$：可整体不选，等价于在“必选分支”基础上再与“空分支”做一次分支比较，即将映射与一个全 0 映射一并做最小值运算。

3. 整合结果 根节点调用 $f(root)$ 得到每个关键词的最低出现次数映射，剔除出现次数为 0 的关键词（即非必选），然后按关键词字母顺序输出。

cpp

#include <bits/stdc++.h>
using namespace std;

// 抽象基类：表达式节点
struct Node {
    virtual unordered_map<string,int> calc() = 0;
    virtual ~Node() = default;
};

// 普通关键词节点
struct TokenNode : Node {
    string tok;
    TokenNode(const string& s) : tok(s) {}
    unordered_map<string,int> calc() override {
        return {{tok, 1}};
    }
};

// 顺序节点：依次执行多个子节点
struct SequenceNode : Node {
    vector<Node*> children;
    unordered_map<string,int> calc() override {
        unordered_map<string,int> res;
        for (auto* c : children) {
            auto m = c->calc();
            for (auto& [k,v] : m) {
                res[k] += v;
            }
        }
        return res;
    }
    ~SequenceNode() { for (auto* c: children) delete c; }
};

// 分支节点：必选或可选
struct BranchNode : Node {
    vector<Node*> options;
    bool required; // true 表示 { … }，false 表示 [ … ]
    unordered_map<string,int> calc() override {
        vector<unordered_map<string,int>> ms;
        for (auto* opt : options)
            ms.push_back(opt->calc());
        if (!required) {
            // 可选：加入一个空分支
            ms.push_back({});
        }
        // 对所有分支取关键词最小值
        unordered_map<string,int> res;
        // 收集所有关键词
        set<string> keys;
        for (auto& m: ms)
            for (auto& [k,_]: m)
                keys.insert(k);
        for (auto& k: keys) {
            int mn = INT_MAX;
            for (auto& m: ms) {
                mn = min(mn, m.count(k) ? m[k] : 0);
            }
            if (mn>0) res[k] = mn;
        }
        return res;
    }
    ~BranchNode() { for (auto* c: options) delete c; }
};

// 全局变量：令牌列表及指针
vector<string> T;
int pos = 0;

// 解析一个节点（可能是序列或单一）
Node* parseNode();

// 解析分支 { … } 或 [ … ]
BranchNode* parseBranch() {
    bool req = (T[pos] == "{");
    pos++; // 跳过 { 或 [
    BranchNode* bn = new BranchNode();
    bn->required = req;
    // 分支内部其实是若干选项，以 '|' 分隔
    while (pos < T.size() && (req ? T[pos]!="}" : T[pos]!="]")) {
        // 解析一个选项序列
        SequenceNode* seq = new SequenceNode();
        while (pos < T.size() && T[pos]!="|" && T[pos]!=(req? "}" : "]")) {
            if (T[pos]=="{" || T[pos]=="[") {
                seq->children.push_back(parseBranch());
            } else {
                seq->children.push_back(new TokenNode(T[pos]));
                pos++;
            }
        }
        bn->options.push_back(seq);
        if (T[pos] == "|") pos++;
    }
    pos++; // 跳过 } 或 ]
    return bn;
}

// 解析整个表达式为序列节点
Node* parseNode() {
    SequenceNode* seq = new SequenceNode();
    while (pos < T.size()) {
        if (T[pos] == "{" || T[pos] == "[") {
            seq->children.push_back(parseBranch());
        } else if (T[pos] == "}" || T[pos] == "]" || T[pos] == "|") {
            break;
        } else {
            seq->children.push_back(new TokenNode(T[pos]));
            pos++;
        }
    }
    return seq;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入整行并分词
    string line;
    getline(cin, line);
    istringstream iss(line);
    string w;
    while (iss >> w) T.push_back(w);

    // 构建语法树
    Node* root = parseNode();
    // 计算最小出现次数映射
    auto mp = root->calc();
    delete root;

    // 只保留出现次数 ≥1 的关键词
    vector<pair<string,int>> ans;
    for (auto& [k,v]: mp) if (v>0) ans.emplace_back(k,v);
    sort(ans.begin(), ans.end(),
         [](auto& a, auto& b){ return a.first < b.first; });

    // 输出
    for (int i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i].first;
    }
    cout << "\n";
    for (int i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i].second;
    }
    cout << "\n";
    return 0;
}

python

# Python 版本
import sys
sys.setrecursionlimit(10000)

# 读入并分词
tokens = sys.stdin.read().strip().split()
pos = 0

class Node:
    def calc(self): pass

class TokenNode(Node):
    def __init__(self, tok): self.tok = tok
    def calc(self):
        return {self.tok: 1}

class SequenceNode(Node):
    def __init__(self): self.children = []
    def calc(self):
        res = {}
        for c in self.children:
            for k,v in c.calc().items():
                res[k] = res.get(k, 0) + v
        return res

class BranchNode(Node):
    def __init__(self, required): self.required = required; self.options = []
    def calc(self):
        maps = [opt.calc() for opt in self.options]
        if not self.required:
            maps.append({})
        keys = set(k for m in maps for k in m)
        res = {}
        for k in keys:
            mn = min(m.get(k,0) for m in maps)
            if mn>0: res[k] = mn
        return res

def parse_branch():
    global pos
    req = tokens[pos] == '{'
    pos += 1
    bn = BranchNode(req)
    while tokens[pos] != ('}' if req else ']'):
        seq = SequenceNode()
        while tokens[pos] not in ['|', '}', ']']:
            if tokens[pos] in ['{','[']:
                seq.children.append(parse_branch())
            else:
                seq.children.append(TokenNode(tokens[pos]))
                pos += 1
        bn.options.append(seq)
        if tokens[pos] == '|': pos += 1
    pos += 1
    return bn

def parse_node():
    global pos
    seq = SequenceNode()
    while pos < len(tokens) and tokens[pos] not in ['}',''] :
        if tokens[pos] in ['{','[']:
            seq.children.append(parse_branch())
        elif tokens[pos] in ['}','|',']']:
            break
        else:
            seq.children.append(TokenNode(tokens[pos]))
            pos += 1
    return seq

root = parse_node()
mp = root.calc()
ans = sorted((k,v) for k,v in mp.items() if v>0)
print(' '.join(k for k,_ in ans))
print(' '.join(str(v) for _,v in ans))

java

import java.util.*;

public class Main {
    static List<String> T;
    static int pos;

    interface Node {
        Map<String,Integer> calc();
    }

    static class TokenNode implements Node {
        String tok;
        TokenNode(String t){ tok=t; }
        public Map<String,Integer> calc(){
            return Collections.singletonMap(tok,1);
        }
    }

    static class SequenceNode implements Node {
        List<Node> ch = new ArrayList<>();
        public Map<String,Integer> calc(){
            Map<String,Integer> res = new HashMap<>();
            for (Node n: ch) {
                for (var e: n.calc().entrySet()){
                    res.put(e.getKey(), res.getOrDefault(e.getKey(),0)+e.getValue());
                }
            }
            return res;
        }
    }

    static class BranchNode implements Node {
        boolean req;
        List<Node> opts = new ArrayList<>();
        BranchNode(boolean r){ req=r; }
        public Map<String,Integer> calc(){
            List<Map<String,Integer>> ms = new ArrayList<>();
            for (Node n: opts) ms.add(n.calc());
            if (!req) ms.add(new HashMap<>()); 
            Set<String> keys = new HashSet<>();
            for (var m: ms) keys.addAll(m.keySet());
            Map<String,Integer> res = new HashMap<>();
            for (String k: keys){
                int mn = Integer.MAX_VALUE;
                for (var m: ms) mn = Math.min(mn, m.getOrDefault(k,0));
                if (mn>0) res.put(k,mn);
            }
            return res;
        }
    }

    static Node parseNode(){
        SequenceNode seq = new SequenceNode();
        while (pos < T.size()) {
            String tk = T.get(pos);
            if (tk.equals("{") || tk.equals("[")) {
                seq.ch.add(parseBranch());
            } else if (tk.equals("}")||tk.equals("]")||tk.equals("|")) {
                break;
            } else {
                seq.ch.add(new TokenNode(tk));
                pos++;
            }
        }
        return seq;
    }

    static BranchNode parseBranch(){
        boolean req = T.get(pos).equals("{");
        pos++;
        BranchNode bn = new BranchNode(req);
        while (!(T.get(pos).equals(req? "}" : "]"))) {
            SequenceNode seq = new SequenceNode();
            while (!T.get(pos).equals("|") && !T.get(pos).equals("}") && !T.get(pos).equals("]")) {
                if (T.get(pos).equals("{")||T.get(pos).equals("[")){
                    seq.ch.add(parseBranch());
                } else {
                    seq.ch.add(new TokenNode(T.get(pos)));
                    pos++;
                }
            }
            bn.opts.add(seq);
            if (T.get(pos).equals("|")) pos++;
        }
        pos++;
        return bn;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        T = Arrays.asList(sc.nextLine().split("\\s+"));
        pos = 0;
        Node root = parseNode();
        Map<String,Integer> mp = root.calc();
        List<String> keys = new ArrayList<>();
        for (var e: mp.entrySet()) if (e.getValue()>0) keys.add(e.getKey());
        Collections.sort(keys);
        for (int i=0;i<keys.size();i++){
            if (i>0) System.out.print(" ");
            System.out.print(keys.get(i));
        }
        System.out.println();
        for (int i=0;i<keys.size();i++){
            if (i>0) System.out.print(" ");
            System.out.print(mp.get(keys.get(i)));
        }
        System.out.println();
    }
}

题目内容

在 $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 ] }

输出

a b c d e f n
4 9 6 10 5 8 9