### Day15:1.202303-3
#### 1.202303-3:LDAP(大模拟，字符串解析)
此题和[[CCF-CSP认证考试准备第十四天 201912-3 化学方程式]]都是字符串解析，但不一样，**201912-3 化学方程式难点在于嵌套括号结合要用到栈**，但**本题难点在于如何储存用户的DN,用户所具有的属性编号和属性编号的值三者关系来条件判断，没有嵌套括号，只有一层括号，所以不需要使用栈**，**但两道题目核心都是字符串解析，先解析大的结构，然后每个大的里面解析小的结构**
(1)20分+运行超时（因为后面的输入没写就一直出不来）->40分，2.046s->看满分代码学习
(2)题目分析与满分代码:
1.题目要求寻找与对应的匹配表达式相匹配的用户的 DN，由小到大排序。考虑集合set（默认升序）或者数组vector(要sort排序)
2.一个匹配表达式可以是一个属性的值，也可以是多个匹配表达式的逻辑组合。这句话就告诉了多个匹配表达式的逻辑组合是大的结构（分为与（`&`）和或（`|`），可以转化为集合的交集和并集），而每个小结构为匹配一个属性的值的表达式（分为断言和反断言）
3.解析每个小结构里面的条件就是根据断言和反断言的定义来决定的：
断言操作符为 `:`，表示匹配具有该属性且值与之相等的用户；
反断言操作符为 `~`，表示匹配具有该属性且值与之不等的用户。
**数据结构的判断**：**我们的目的是获取用户SN集合，因此它为插入的结果，应该放在map最后面
首先判断匹配具有该属性,且断言和反断言都要判断，因此创建一个`map<int, set<int>> attrName_users;` 表示该属性名对应的所有用户DN
接着判断该属性的值与输入的值是否相等，因此还要创建一个`map<int, map<int, set<int>>> attrName_attrVal_users;` 实现了属性名-属性值-用户DN集合的映射**
(3)代码：
```
#include <bits/stdc++.h>
using namespace std;
map<int,set<int>> shu_users;//属性-用户集合
map<int,map<int,set<int>>> shu_val_users;//属性-值-用户集合
int string2digit(string &s,int &index){//引用index,直接跳过数字部分
int num=0;
while(index<s.size() && isdigit(s[index])){
num=num*10+s[index]-'0';
index++;
}
return num;
}
set<int> yuanZi(string &s,int &index){
set<int> res;
int shu=string2digit(s,index);//index在 string2digit函数内部已经改变
char op=s[index++];
int val=string2digit(s,index);
if(op==':'){
if(shu_val_users.count(shu) && shu_val_users[shu].count(val)){//表示匹配具有该属性且值与之相等(存在该值)
res.insert(shu_val_users[shu][val].begin(),shu_val_users[shu][val].end());//把原先有的用户集合全部放入res集合中
}
}
else if(op=='~'){
if(shu_users.count(shu)){//表示匹配具有该属性
res.insert(shu_users[shu].begin(),shu_users[shu].end());//先插入（不要赋值，不确定有几个表达式）之后删除，因为map只能获取里面有的元素
if(shu_val_users[shu].count(val)){//属性有这个值才去遍历此时的用户集合并在res中删去
for(auto x:shu_val_users[shu][val]){//后面为一个set<int>,前面x为int类型
res.erase(x);
}
}
}
}
return res;
}
set<int> biaoDaShi(string &s,int &index){
set<int> res;
if(isdigit(s[index])){//解析原子表达式
return yuanZi(s,index);
}
else if(s[index]=='&' || s[index]=='|'){//解析含有逻辑的匹配表达式
char op=s[index++];
index++;//跳过左括号
set<int> tmp1=biaoDaShi(s,index);//递归调用,运行完index处在右括号位置
index++;//跳过右括号
index++;//跳过左括号
set<int> tmp2=biaoDaShi(s,index);
index++;//跳过右括号
if(op=='&'){
//处理交集
for(auto &x:tmp1){
if(tmp2.count(x)){
res.insert(x);
}
}
}
else if(op=='|'){
//处理并集(集合插入重复元素相当于未插入)
res.insert(tmp1.begin(),tmp1.end());
res.insert(tmp2.begin(),tmp2.end());
}
}
return res;
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++){
int DN,num;
cin>>DN>>num;
while(num--){
int shu,val;
cin>>shu>>val;
shu_users[shu].insert(DN);
shu_val_users[shu][val].insert(DN);
}
}
int m;
cin>>m;
cin.ignore();
while(m--){
string s;
getline(cin,s);
int index=0;
set<int> res=biaoDaShi(s,index);
for(auto &x:res){
cout<<x<<" ";
}
cout<<endl;
}
return 0;
}
```
(4)注意:
1.本题index函数形参都为引用，方便直接函数内部改变（因为是顺序遍历字符串），不用回到调用方再改变，且函数尽量都有index引用形参，index的初始化放在main中
2.本题思路是先提取属性，字符op和属性值后再判断op并进行相应操作（因为不同的op都是相同的属性和属性值，只有操作不同），而不是先判断op然后分条件操作
3.set并集和交集的操作
```
if(op=='&'){
//处理交集
for(auto &x:tmp1){
if(tmp2.count(x)){
res.insert(x);
}
}
}
else if(op=='|'){
//处理并集(集合插入重复元素相当于未插入)
res.insert(tmp1.begin(),tmp1.end());
res.insert(tmp2.begin(),tmp2.end());
}
```
4.将一个集合全部放进另一个set集合中直接insert即可（无需判断是否重复），map和set查询都可以用count()方法
5.index跳过左右括号和**递归调用解析表达式**
```
char op=s[index++];
index++;//跳过左括号
set<int> tmp1=biaoDaShi(s,index);//递归调用,运行完index处在右括号位置
index++;//跳过右括号
index++;//跳过左括号
set<int> tmp2=biaoDaShi(s,index);
index++;//跳过右括号
```