热线服务自动回答系统问题解析

这道题目要求我们实现一个自适应回答系统（AAAAA模块），该系统需要处理用户的陈述句和疑问句，并根据规则生成相应回答。问题涉及自然语言处理和规则匹配，需要仔细处理各种语法规则和逻辑判断。

核心数据结构与设计思路

1. 数据结构设计：

   • node结构体：存储陈述句中的动词、宾语、肯定/否定标志和出现顺序
   • map<string, vector<node>>：按主语存储对应的陈述句
   • vector<node>：存储通用主语$（everybody/nobody）$的陈述句

2. 关键映射：

   • rev映射：处理"$I$"和"$you$"在问答中的转换$（I→you，you→I）$

核心算法解析

1. 句子解析：

   • 将输入句子按空格分割成单词向量
   • 处理标点符号（移除句点/问号）
   • 识别句子类型（陈述句/疑问句）和结构

2. 陈述句处理：

   • 提取主语、动词、宾语
   • 处理否定形式$（don't/doesn't）$
   • 处理通用主语$（everybody/nobody）$
   • 检测陈述矛盾（相同主语+动词+宾语的正反陈述）

3. 疑问句处理：

   • 类型1：do/does subject predicate [object] ?
     • 检查是否存在对应主语的肯定/否定陈述
   • 类型2：who predicates [object] ?
     • 查找所有满足条件的主语，按出现顺序排序
     • 处理"$everybody$"和"$nobody$"特殊情况
   • 类型3：what do/does subject do ?
     • 收集主语的所有动作，去重后按顺序输出

4. 动词形式处理：

   • calc函数：根据主语确定动词形式（加$s$或不加）
   • work函数：处理助动词$（do/does）$和动词形式转换

代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;


int Case;
map<string, string> rev;

string oqs(string s) {
	return (s == "I" || s == "you" ? rev[s] : s);
}

struct node {
	string a, b;
	bool fg;
	int id;
	bool operator<(const node h) const {
		return id < h.id;
	}
	bool operator==(node h) {
		return ((a == h.a) && (b == h.b));
	}
};

int wk(string s) {
	if (s == "I" || s == "me") return 1;
	if (s == "you") return 2;
	return 3; 
}

string work(string s) {
	if (s.size() >= 2 && s[0] == 'd' && s[1] == 'o') {
		if (s.size() >= 4 && s[2] == 'e' && s[3] == 's') {
			if (s.size() == 4) {
				s.erase(2, 2);
			} else {
				s[2] = s[4];
				s[3] = s[5];
				s[4] = s[6];
				s.erase(5, 2);
			}
		}
	}
	
	if (!s.empty() && s[s.size()-1] == 's') {
		s.erase(s.size() - 1, 1);
	}
	return s;
}

bool check(string ss) {
	return (ss == "is") || (ss == "are") || (ss == "am");
}

string calc(string ss, string s) {
	if (oqs(ss) == ss) {
		if (s == "do") {
			return "does";
		}
		if (s == "don't") {
			return "doesn't";
		}
		if (check(s)) {
			return "is";
		}
		return s + "s";
	}
	if (check(s)) {
		if (ss == "I") {
			return "am";
		}
		return "are";
	}
	return s;
}

struct nd {
	int id;
	string s;
	bool operator < (nd a) const {
		return id < a.id;
	}
};

void solve() {
	string ss;
	vector<node> all;
	map<string, vector<node> > m;
	Case++;
	cout << "Dialogue #" << Case << ":\n";
	getline(cin, ss);
	bool nope = 0;
	int Id = 0;
	
	while (ss[ss.size()-1] != '!') {
		Id++;
		vector<string> dw;
		string tmp = "";
		int idd = 1, st = 0;
		
		for (size_t i = 0; i < ss.size(); i++) {
			if (ss[i] == ' ' && st <= idd) {
				dw.push_back(tmp);
				st++;
				if (tmp == "don't" || tmp == "doesn't") {
					idd++;
				}
				tmp = "";
			} else {
				tmp += ss[i];
			}
		}
		
		if (!tmp.empty()) tmp.erase(tmp.size() - 1, 1);
		dw.push_back(tmp);
		dw.push_back("");
		dw.push_back("");
		dw.push_back("");
		
		if (ss[ss.size()-1] == '.') {
			ss.erase(ss.size() - 1, 1);
			if (dw[0] == "I" || dw[0] == "you") dw[0] = rev[dw[0]];
			dw[1] = work(dw[1]);
			if (check(dw[1])) dw[1] = "is";
			bool ff = 1;
			
			if (dw[0] == "nobody") {
				ff = !ff;
			}
			if (dw[1] == "don't") {
				dw[2] = work(dw[2]);
				ff = !ff;
			}
			
			if (dw[0] != "nobody" && dw[0] != "everybody" && dw[1] != "don't") {
				node n;
				n.a = dw[1]; n.b = dw[2]; n.fg = ff; n.id = Id;
				m[dw[0]].push_back(n);
				for (size_t i = 0; i < m[dw[0]].size(); i++) {
					node n = m[dw[0]][i];
					if (n.a == dw[1] && n.b == dw[2] && n.fg != ff) {
						nope = 1;
						break;
					}
				}
				for (size_t i = 0; i < all.size(); i++) {
					node n = all[i];
					if (n.a == dw[1] && n.b == dw[2] && n.fg != ff) {
						nope = 1;
						break;
					}
				}
			} else if (dw[0] != "nobody" && dw[0] != "everybody") {
				node n;
				n.a = dw[2]; n.b = dw[3]; n.fg = ff; n.id = Id;
				m[dw[0]].push_back(n);
				for (size_t i = 0; i < m[dw[0]].size(); i++) {
					node n = m[dw[0]][i];
					if (n.a == dw[2] && n.b == dw[3] && n.fg != ff) {
						nope = 1;
						break;
					}
				}
				for (size_t i = 0; i < all.size(); i++) {
					node n = all[i];
					if (n.a == dw[2] && n.b == dw[3] && n.fg != ff) {
						nope = 1;
						break;
					}
				}
			} else {
				node n;
				n.a = dw[1]; n.b = dw[2]; n.fg = ff; n.id = Id;
				all.push_back(n);
				for (size_t i = 0; i < all.size(); i++) {
					node n = all[i];
					if (n.a == dw[1] && n.b == dw[2] && n.fg != ff) {
						nope = 1;
						break;
					}
				}
				for (map<string, vector<node> >::iterator it = m.begin(); it != m.end(); ++it) {
					vector<node> w = it->second;
					for (size_t i = 0; i < w.size(); i++) {
						node n = w[i];
						if (n.a == dw[1] && n.b == dw[2] && n.fg != ff) {
							nope = 1;
							break;
						}
					}
				}
			}
		} else {
			cout << ss << endl;
			ss.erase(ss.size() - 1, 1);
			
			if (nope) {
				cout << "I am abroad.\n\n";
				getline(cin, ss);
				continue;
			}
			
			if (dw[0].size() >= 2 && dw[0][0] == 'd' && dw[0][1] == 'o') {
				bool fuck = 0;
				if (dw[1] == "nobody") fuck = 1; 
				string t1 = "", t2 = "";
				bool f = 0;
				
				for (size_t i = 0; i < dw[2].size(); i++) {
					if (f == 0 && dw[2][i] == ' ') {
						t1 = dw[2].substr(0, i);
						f = 1;
						continue;
					}
					if (f) t2 += dw[2][i];
				}
				
				if (f) {
					dw[2] = t1;
					dw[3] = t2;
				}
				
				dw[1] = oqs(dw[1]);
				dw[0] = work(dw[0]);
				dw[2] = work(dw[2]);
				int ff = 0;
				
				for (size_t i = 0; i < m[dw[1]].size(); i++) {
					node n = m[dw[1]][i];
					if (ff == 0 && n.a == dw[2] && n.b == dw[3]) {
						if (ff == 0 && (n.fg ^ fuck) == 1) {
							string ss = dw[1] + ' ';
							ss += calc(dw[1], dw[2]);
							if (dw[3] != "") ss += ' ' + dw[3];
							cout << "yes, " << ss << '.' << endl;
							ff = 1;
						} else if (ff == 0) {
							string ss = dw[1] + ' ';
							string dww = "do";
							ss += calc(dw[1], dww);
							ss += "n't " + dw[2];
							if (dw[3] != "") ss += ' ' + dw[3];
							cout << "no, " << ss << '.' << endl;
							ff = 1;
						}
					}
				}
				
				for (size_t i = 0; i < all.size(); i++) {
					node n = all[i];
					if (ff == 0 && n.a == dw[2] && n.b == dw[3]) {
						if ((n.fg ^ fuck) == 1) {
							string ss = dw[1] + ' ';
							ss += calc(dw[1], dw[2]);
							if (dw[3] != "") ss += ' ' + dw[3];
							cout << "yes, " << ss << '.' << endl;
							ff = 1;
						} else {
							string ss = dw[1] + ' ';
							string ssh = "do";
							ss += calc(dw[1], ssh);
							ss += "n't " + dw[2];
							if (dw[3] != "") ss += ' ' + dw[3];
							cout << "no, " << ss << '.' << endl;
							ff = 1;
						}
					}
				}
				
				if (!ff) cout << "maybe." << endl;
			}
			
			if (dw[0] == "who") {
				dw[1] = work(dw[1]);
				if (check(dw[1])) dw[1] = "is";
				vector<nd> ans;
				bool fg = 0;
				
				for (size_t i = 0; i < all.size(); i++) {
					node w = all[i];
					if (w.a == dw[1] && w.b == dw[2]) {
						string w1 = "everybody";
						string w2 = "nobody";
						nd a;
						a.id = w.id;
						a.s = w.fg ? w1 : w2;
						ans.push_back(a);
						fg = 1;
						break;
					}
				}
				
				if (fg) {
					cout << ans[0].s << ' ' << calc(ans[0].s, dw[1]);
					if (dw[2] != "") cout << " " << dw[2];
					cout << ".\n";
					
					cout << '\n';
					getline(cin, ss);
					continue;
				}
				
				for (map<string, vector<node> >::iterator it = m.begin(); it != m.end(); ++it) {
					string u = it->first;
					vector<node> v = it->second;
					for (size_t i = 0; i < v.size(); i++) {
						node w = v[i];
						if (w.a == dw[1] && w.b == dw[2] && w.fg) {
							nd a;
							a.id = w.id;
							a.s = u;
							ans.push_back(a);
							break;
						}
					}
				}
				
				if (dw[2] == "I") dw[2] = "you";
				else if (dw[2] == "you") dw[2] = "I";
				
				sort(ans.begin(), ans.end());
				
				if (ans.empty()) {
					cout << "I don't know.\n";
				} else if (ans.size() == 1) {
					string ssh = dw[1];
					ssh = calc(ans[0].s, ssh);
					cout << ans[0].s << ' ';
					cout << ssh;
					ssh = dw[2];
					if (ssh == "I") ssh = "you";
					else if (ssh == "you") ssh = "me";
					if (dw[2] != "") cout << ' ' << ssh;
					cout << ".\n";
				} else {
					for (size_t i = 0; i < ans.size(); i++) {
						string outp = (i >= ans.size() - 2 ? " " : ", ");
						if (i != ans.size() - 1) {
							cout << ans[i].s << outp;
						} else {
							cout << "and " << ans[i].s << ' ';
						}
					}
					cout << dw[1];
					string ssh = dw[2];
					if (ssh == "I") ssh = "you";
					else if (ssh == "you") ssh = "me";
					if (dw[2] != "") cout << ' ' << ssh;
					cout << ".\n";
				}  
			}
			
			if (dw[0] == "what") {
				bool fuck = 0;
				for (size_t i = 0; i < dw[2].size(); i++) {
					if (dw[2][i] == ' ') {
						dw[2] = dw[2].substr(0, i);
						break;
					}
				}
				if (dw[2] == "nobody") fuck = 1; 
				bool ff = (oqs(dw[2]) == dw[2]);
				dw[2] = oqs(dw[2]);
				vector<node> ans;
				
				if (m.find(dw[2]) != m.end()) {
					vector<node> v = m[dw[2]];
					for (size_t i = 0; i < v.size(); i++) {
						ans.push_back(v[i]);
					}
				}
				for (size_t i = 0; i < all.size(); i++) {
					ans.push_back(all[i]);
				}
				
				if (ans.empty()) {
					cout << "I don't know.\n";
					cout << '\n';
					getline(cin, ss);
					continue;
				}
				
				sort(ans.begin(), ans.end());
				vector<node>::iterator it = unique(ans.begin(), ans.end());
				ans.resize(distance(ans.begin(), it));
				cout << dw[2] << ' ';
				
				if (ans.size() == 1) {
					if (!(ans[0].fg ^ fuck)) {
						cout << (ff ? "doesn't" : "don't") << ' ' << ans[0].a;
						if (ans[0].b != "") cout << ' ' << ans[0].b;
						cout << ".\n";
					} else {
						cout << (calc(dw[2], ans[0].a));
						if (ans[0].b != "") cout << ' ' << ans[0].b;
						cout << ".\n";
					}
					cout << '\n';
					getline(cin, ss);
					continue;
				}
				
				for (size_t i = 0; i < ans.size(); i++) {
					string outp = ", ";
					if (i != ans.size() - 1) {
						if (!(ans[i].fg ^ fuck)) {
							cout << (ff ? "doesn't" : "don't") << ' ' << ans[i].a;
							if (ans[i].b != "") cout << ' ' << ans[i].b;
							cout << outp;
						} else {
							cout << (ff ? calc(dw[2], ans[i].a) : ans[i].a);
							if (ans[i].b != "") cout << ' ' << ans[i].b;
							cout << outp;
						}
					} else {
						cout << "and ";
						if (!(ans[i].fg ^ fuck)) {
							cout << (ff ? "doesn't" : "don't") << ' ' << ans[i].a;
							if (ans[i].b != "") cout << ' ' << ans[i].b;
							cout << ".\n";
						} else {
							cout << (ff ? calc(dw[2], ans[i].a) : ans[i].a);
							if (ans[i].b != "") cout << ' ' << ans[i].b;
							cout << ".\n";
						}
					}
				}
			}
			cout << '\n';
		}
		getline(cin, ss);
	}
	cout << ss << "\n\n";
}

int main() {
	rev["I"] = "you";
	rev["you"] = "I";
	int T;
	cin >> T;
	string ss;
	getline(cin, ss);
	while (T--) solve();
	return 0;
}

复杂度分析

• 时间复杂度：O(N×M)，N为句子数量，M为每个句子的单词数
• 空间复杂度：O(N)，存储所有陈述句和中间数据