命令行解析与出现次数统计
题意
给定一个命令行模板字符串，由关键词（纯小写字母）、选择结构 {A | B | ...} 和可选结构 [C] 组成，支持嵌套。
需要完成两件事：
- 找出模板最外层（不被任何
{}或[]包裹）的所有关键词，按出现顺序输出（同一个词出现多次就输出多次）。 - 对每个关键词，计算它在任意合法命令中保证出现的最少次数。
计算规则：
- 顶层直接出现的关键词，保证出现 1 次。
- 选择结构
{A | B | C}：如果某个关键词在每个分支里都保证出现，那么取各分支中的最小保证次数，加到结果里。 - 可选结构
[...]：里面的内容可以不出现，所以不贡献任何保证次数。
思路
这道题本质上是一个递归下降解析问题。模板字符串有嵌套结构，天然适合用递归来处理。
先想清楚每一层要返回什么。对于模板中的一段序列，我们需要返回一个映射：每个关键词在这段序列中的"保证出现次数"。
然后分三种情况讨论：
- 纯关键词：直接计数 +1。
- 选择结构
{...}：用|分隔出若干分支，递归解析每个分支。一个关键词要想"保证出现"，它必须在每个分支中都保证出现——取所有分支中的最小值。 - 可选结构
[...]：递归解析里面的内容，但结果直接丢弃，因为可选意味着可以不出现。
解析器的实现就是标准的递归下降。维护一个全局指针 pos，遇到 { 就进入选择结构的解析，遇到 [ 就进入可选结构的解析，遇到 }、]、| 就返回当前结果。
至于输出的第一行（固定关键词列表），单独做一趟扫描就行：维护一个深度计数器，遇到 { 或 [ 加 1，遇到 } 或 ] 减 1，只在深度为 0 时收集关键词。注意同一个关键词如果在顶层出现了多次，要重复输出。
时间复杂度 ，其中
是模板字符串长度，每个 token 最多被访问常数次。
代码
#include <bits/stdc++.h>
using namespace std;
vector<string> tokenize(const string& s) {
vector<string> tokens;
string cur;
for (char c : s) {
if (c == '{' || c == '}' || c == '[' || c == ']' || c == '|') {
if (!cur.empty()) { tokens.push_back(cur); cur.clear(); }
tokens.push_back(string(1, c));
} else if (c == ' ') {
if (!cur.empty()) { tokens.push_back(cur); cur.clear(); }
} else {
cur += c;
}
}
if (!cur.empty()) tokens.push_back(cur);
return tokens;
}
int pos;
vector<string> tokens;
bool isKeyword(const string& s) {
for (char c : s) if (!islower(c)) return false;
return !s.empty();
}
map<string, int> parseSequence(bool stopOnPipe, bool stopOnBrace, bool stopOnBracket) {
map<string, int> res;
while (pos < (int)tokens.size()) {
const string& t = tokens[pos];
if (stopOnPipe && t == "|") break;
if (stopOnBrace && t == "}") break;
if (stopOnBracket && t == "]") break;
if (t == "{") {
pos++;
vector<map<string, int>> options;
while (true) {
auto opt = parseSequence(true, true, false);
options.push_back(opt);
if (pos < (int)tokens.size() && tokens[pos] == "|") pos++;
else break;
}
if (pos < (int)tokens.size() && tokens[pos] == "}") pos++;
set<string> allKeys;
for (auto& opt : options)
for (auto& p : opt) allKeys.insert(p.first);
for (const string& key : allKeys) {
int mn = INT_MAX;
for (auto& opt : options) {
auto it = opt.find(key);
if (it == opt.end()) { mn = 0; break; }
mn = min(mn, it->second);
}
if (mn > 0) res[key] += mn;
}
} else if (t == "[") {
pos++;
parseSequence(false, false, true);
if (pos < (int)tokens.size() && tokens[pos] == "]") pos++;
} else if (isKeyword(t)) {
res[t]++;
pos++;
} else {
pos++;
}
}
return res;
}
int main() {
string line;
getline(cin, line);
tokens = tokenize(line);
vector<string> fixed;
int depth = 0;
for (const string& t : tokens) {
if (t == "{" || t == "[") depth++;
else if (t == "}" || t == "]") depth--;
else if (depth == 0 && isKeyword(t)) fixed.push_back(t);
}
pos = 0;
auto res = parseSequence(false, false, false);
for (int i = 0; i < (int)fixed.size(); i++) {
if (i) cout << " ";
cout << fixed[i];
}
cout << "\n";
for (int i = 0; i < (int)fixed.size(); i++) {
if (i) cout << " ";
cout << res[fixed[i]];
}
cout << "\n";
}
import java.util.*;
public class Main {
static List<String> tokens;
static int pos;
static List<String> tokenize(String s) {
List<String> res = new ArrayList<>();
StringBuilder cur = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '{' || c == '}' || c == '[' || c == ']' || c == '|') {
if (cur.length() > 0) { res.add(cur.toString()); cur.setLength(0); }
res.add(String.valueOf(c));
} else if (c == ' ') {
if (cur.length() > 0) { res.add(cur.toString()); cur.setLength(0); }
} else {
cur.append(c);
}
}
if (cur.length() > 0) res.add(cur.toString());
return res;
}
static boolean isKeyword(String s) {
if (s.isEmpty()) return false;
for (char c : s.toCharArray()) if (c < 'a' || c > 'z') return false;
return true;
}
static Map<String, Integer> parseSequence(boolean stopPipe, boolean stopBrace, boolean stopBracket) {
Map<String, Integer> res = new HashMap<>();
while (pos < tokens.size()) {
String t = tokens.get(pos);
if (stopPipe && t.equals("|")) break;
if (stopBrace && t.equals("}")) break;
if (stopBracket && t.equals("]")) break;
if (t.equals("{")) {
pos++;
List<Map<String, Integer>> options = new ArrayList<>();
while (true) {
Map<String, Integer> opt = parseSequence(true, true, false);
options.add(opt);
if (pos < tokens.size() && tokens.get(pos).equals("|")) pos++;
else break;
}
if (pos < tokens.size() && tokens.get(pos).equals("}")) pos++;
Set<String> allKeys = new HashSet<>();
for (Map<String, Integer> opt : options) allKeys.addAll(opt.keySet());
for (String key : allKeys) {
int mn = Integer.MAX_VALUE;
for (Map<String, Integer> opt : options) {
if (!opt.containsKey(key)) { mn = 0; break; }
mn = Math.min(mn, opt.get(key));
}
if (mn > 0) res.merge(key, mn, Integer::sum);
}
} else if (t.equals("[")) {
pos++;
parseSequence(false, false, true);
if (pos < tokens.size() && tokens.get(pos).equals("]")) pos++;
} else if (isKeyword(t)) {
res.merge(t, 1, Integer::sum);
pos++;
} else {
pos++;
}
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
tokens = tokenize(line);
List<String> fixed = new ArrayList<>();
int depth = 0;
for (String t : tokens) {
if (t.equals("{") || t.equals("[")) depth++;
else if (t.equals("}") || t.equals("]")) depth--;
else if (depth == 0 && isKeyword(t)) fixed.add(t);
}
pos = 0;
Map<String, Integer> res = parseSequence(false, false, false);
StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();
for (int i = 0; i < fixed.size(); i++) {
if (i > 0) { sb1.append(" "); sb2.append(" "); }
sb1.append(fixed.get(i));
sb2.append(res.getOrDefault(fixed.get(i), 0));
}
System.out.println(sb1);
System.out.println(sb2);
}
}
def tokenize(s):
tokens = []
cur = []
for c in s:
if c in '{|}[]':
if cur:
tokens.append(''.join(cur))
cur = []
tokens.append(c)
elif c == ' ':
if cur:
tokens.append(''.join(cur))
cur = []
else:
cur.append(c)
if cur:
tokens.append(''.join(cur))
return tokens
def is_keyword(s):
return s and all('a' <= c <= 'z' for c in s)
def parse_sequence(tokens, pos, stop_pipe, stop_brace, stop_bracket):
res = {}
while pos < len(tokens):
t = tokens[pos]
if stop_pipe and t == '|': break
if stop_brace and t == '}': break
if stop_bracket and t == ']': break
if t == '{':
pos += 1
options = []
while True:
opt, pos = parse_sequence(tokens, pos, True, True, False)
options.append(opt)
if pos < len(tokens) and tokens[pos] == '|':
pos += 1
else:
break
if pos < len(tokens) and tokens[pos] == '}':
pos += 1
all_keys = set()
for opt in options:
all_keys.update(opt.keys())
for key in all_keys:
mn = float('inf')
for opt in options:
if key not in opt:
mn = 0
break
mn = min(mn, opt[key])
if mn > 0:
res[key] = res.get(key, 0) + mn
elif t == '[':
pos += 1
_, pos = parse_sequence(tokens, pos, False, False, True)
if pos < len(tokens) and tokens[pos] == ']':
pos += 1
elif is_keyword(t):
res[t] = res.get(t, 0) + 1
pos += 1
else:
pos += 1
return res, pos
line = input()
tokens = tokenize(line)
fixed = []
depth = 0
for t in tokens:
if t in ('{', '['):
depth += 1
elif t in ('}', ']'):
depth -= 1
elif depth == 0 and is_keyword(t):
fixed.append(t)
res, _ = parse_sequence(tokens, 0, False, False, False)
print(' '.join(fixed))
print(' '.join(str(res.get(k, 0)) for k in fixed))
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
const tokens = tokenize(line.trim());
const fixed = [];
let depth = 0;
for (const t of tokens) {
if (t === '{' || t === '[') depth++;
else if (t === '}' || t === ']') depth--;
else if (depth === 0 && isKeyword(t)) fixed.push(t);
}
const [res] = parseSequence(tokens, 0, false, false, false);
console.log(fixed.join(' '));
console.log(fixed.map(k => res[k] || 0).join(' '));
rl.close();
});
function tokenize(s) {
const tokens = [];
let cur = '';
for (const c of s) {
if ('{|}[]'.includes(c)) {
if (cur) { tokens.push(cur); cur = ''; }
tokens.push(c);
} else if (c === ' ') {
if (cur) { tokens.push(cur); cur = ''; }
} else {
cur += c;
}
}
if (cur) tokens.push(cur);
return tokens;
}
function isKeyword(s) {
return s.length > 0 && /^[a-z]+$/.test(s);
}
function parseSequence(tokens, pos, stopPipe, stopBrace, stopBracket) {
const res = {};
while (pos < tokens.length) {
const t = tokens[pos];
if (stopPipe && t === '|') break;
if (stopBrace && t === '}') break;
if (stopBracket && t === ']') break;
if (t === '{') {
pos++;
const options = [];
while (true) {
const [opt, newPos] = parseSequence(tokens, pos, true, true, false);
options.push(opt);
pos = newPos;
if (pos < tokens.length && tokens[pos] === '|') pos++;
else break;
}
if (pos < tokens.length && tokens[pos] === '}') pos++;
const allKeys = new Set();
for (const opt of options)
for (const key of Object.keys(opt)) allKeys.add(key);
for (const key of allKeys) {
let mn = Infinity;
for (const opt of options) {
if (!(key in opt)) { mn = 0; break; }
mn = Math.min(mn, opt[key]);
}
if (mn > 0) res[key] = (res[key] || 0) + mn;
}
} else if (t === '[') {
pos++;
const [, newPos] = parseSequence(tokens, pos, false, false, true);
pos = newPos;
if (pos < tokens.length && tokens[pos] === ']') pos++;
} else if (isKeyword(t)) {
res[t] = (res[t] || 0) + 1;
pos++;
} else {
pos++;
}
}
return [res, pos];
}
京公网安备 11010502036488号