NC15692. Database
描述
现在你需要实现一个简单的SQL语句的解释器。
一个数据库中会有若干张表，每张表中包含行与列。
你可以认为一个表就是一个二维数组，在创建时要指定列名，可以动态插入一行。
为了简化问题，规定表中存储的数据都是int类型。
所有语句被简化为三类四种，分别是表创建语句，插入语句，和两种形式的查询语句。
1. create table [tablename] ([column1], [column2], [column3], ....)
创建一个叫tablename的表，并规定列名为column1, column2, column3...
输入数据保证不会创建超过5个表，每个表最多5列
2. insert into [tablename]([column1], [column2], .....) values([values1], [values2], [values3], ....);;
向表里加入一行，values1和column1对应，对于没有指定的列，对应的数值默认为0。
3. select [column1], [column2], [column3], ... from [tablename];
将一个表中某些列的内容输出。
4. select [column1], [column2], [column3], ... from [tablename] where [column] in [set]
从表中选出一些满足条件的列, 并满足where后的条件
set可以是语句3或者语句4的查询结果，且一定是对于单列的查询结果。
所有不带[]的内容都是格式固定不会变动的内容，全部字母都为小写字母。
输入描述
输入数据不超过100行，请处理到EOF。
每行对应四种语句中的一种。
列名和表名中不会有空格。
保证所有语句都是语法正确的。
保证每个逗号后都有一个空格。
保证没有多余的空格
输出描述
对于每一个select语句，输出N行M列。
对于满足条件的行，请按插入顺序输出。
以一个空格分开，请不要输出行末空格。
每输出一个不为空的查询结果，需要再换一行。如果查询结果为空，则仅仅输出一个换行符号。
表示查询结果，具体可参见样例。
示例1
输入:
create table wussy(c1, c2, c3); insert into wussy(c1, c2) values(1, 2); select c1, c2, c3 from wussy; insert into wussy(c1, c2, c3) values(4, 5, 6); create table vampireweekend(c1, c2); insert into vampireweekend(c1) values(1); select c1, c2, c3 from wussy; select c1, c2 from wussy where c1 in select c1 from vampireweekend;
输出:
1 2 0 1 2 0 4 5 6 1 2
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2018-08-21 21:39:05
#include <bits/stdc++.h>
using namespace std;
struct head {
vector <string> col;
};
head h[10]; int cnt = 0;
map <string, int> mapp;
struct data {
int id;
int num;
vector <string> c [100];
int a[10];
};
data d[10];
const char* dem = ", ";
string sub (const string& str, int p, char last) {
int p2 = str.find(last, p);
return str.substr(p, p2 - p);
}
vector <string> split (const string & str) {
vector <string> res;
char *ss = new char[str.size() + 1];
strcpy (ss, str.c_str());
char*p = strtok(ss, dem);
while (p) {
string s = p;
res.push_back(s);
p = strtok(NULL, dem);
}
return res;
}
int find_c (const string& str, const vector <string>& res) {
for (int i = 0; i < res.size(); i++)
if (str == res[i])
return i;
return 0;
}
void m_print (const data& t) {
for (int i = 1; i <= t.num; i++) {
cout << t.c[i][0];
for (int j = 1; j < t.c[i].size(); j++)
cout << " " << t.c[i][j];
cout << endl;
}
cout << endl;
}
void creat (const string& s) {
string ta = sub(s, 13, '(');
int p = s.find('(');
string s1 = sub(s, p + 1, ')');
mapp[ta] = ++cnt;
h[cnt].col = split(s1);
return ;
}
void inser (const string&s) {
string ta = sub(s, 12, '(');
int p1 = s.find('(');
string s1 = sub(s, p1 + 1, ')');
vector <string> r1 = split (s1);
int p2 = s.rfind('(');
string s2 = sub(s, p2 + 1, ')');
vector <string> r2 = split(s2);
int id = mapp[ta]; int len = h[id].col.size();
int k = ++d[id].num;
for (int i = 0; i < len; i++) d[id].c[k].push_back("0");
for (int i = 0; i < r1.size(); i++) {
int t = find_c(r1[i], h[id].col);
d[id].c[k][t] = r2[i];
}
}
data se1 (const string& s) {
data ans; ans.num = 0;
int p1 = s.rfind("from ");
string s1 = s.substr (7, p1 - 8);
vector <string> res = split(s1);
string ta = sub (s, p1 + 5, ';');
int id = mapp[ta];
ans.num = d[id].num;
ans.id = id;
for (int i = 1; i <= ans.num; i++)
for (int j = 0; j < res.size(); j++) {
int k = find_c(res[j], h[id].col);
ans.a[j] = k;
ans.c[i].push_back(d[id].c[i][k]);
}
return ans;
}
data se2 (const string&s ) {
data ans; ans.num = 0;
int p1 = s.find ("where ");
if (p1 == string::npos) return se1(s);
string s1 = s.substr (0, p1);
s1[p1 - 1] = ';'; data t1 = se1(s1);
int p2 = s.find ("in ");
string ss = s.substr(p1 + 6, p2 - 7 - p1);
int k = find_c (ss, h[t1.id].col);
string s2 = s.substr(p2 + 3);
data t2 = se2(s2);
for (int i = 1; i <= t1.num; i++)
for (int j = 1; j <= t2.num; j++)
if ( d[t1.id].c[i][k] == t2.c[j][0]) {
ans.num++;
ans.c[ans.num] = t1.c[i];
break;
}
return ans;
}
int main ()
{
string s;
while (getline(cin, s)) {
if (s[0] == 'c') creat (s);
else if (s[0] == 'i') inser(s);
else if (s[0] == 's' && s.find(" where ") == string::npos) {
data t = se1(s); m_print(t);
}
else {
data t = se2(s); m_print(t);
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2020-03-10 19:09:30
#include<bits/stdc++.h>
using namespace std;
struct head
{
vector<string> col;
};
head h[10];
int cnt=0;
map<string,int> mapp;
struct data
{
int id;
int num;
vector<string> c[100];
int a[10];
};
data d[10];
const char *dem=", ";
string sub(const string& str,int p,char last)
{
int p2=str.find(last,p);
return str.substr(p,p2-p);
}
vector<string> split(const string &str)
{
vector<string> res;
char *ss=new char[str.size()+1];
strcpy(ss,str.c_str());
char *p=strtok(ss,dem);
while(p)
{
string s=p;
res.push_back(s);
p=strtok(NULL,dem);
}
return res;
}
int find_c(const string &str,const vector<string> &res)
{
for(int i=0;i<res.size();i++)
if(str==res[i])
return i;
return 0;
}
void m_print(const data &t)
{
for(int i=1;i<=t.num;i++)
{
cout<<t.c[i][0];
for(int j=1;j<t.c[i].size();j++)
cout<<" "<<t.c[i][j];
cout<<endl;
}
cout<<endl;
}
void creat (const string& s)
{
string ta=sub(s,13,'(');
int p=s.find('(');
string s1=sub(s,p+1,')');
mapp[ta]=++cnt;
h[cnt].col=split(s1);
return;
}
void inser(const string &s)
{
string ta=sub(s,12,'(');
int p1=s.find('(');
string s1=sub(s,p1+1,')');
vector<string> r1=split(s1);
int p2=s.rfind('(');
string s2=sub(s,p2+1,')');
vector<string> r2=split(s2);
int id=mapp[ta];
int len=h[id].col.size();
int k=++d[id].num;
for(int i=0;i<len;i++) d[id].c[k].push_back("0");
for(int i=0;i<r1.size();i++)
{
int t=find_c(r1[i],h[id].col);
d[id].c[k][t]=r2[i];
}
}
data se1(const string& s)
{
data ans;
ans.num=0;
int p1=s.rfind("from ");
string s1=s.substr(7,p1-8);
vector<string> res=split(s1);
string ta=sub(s,p1+5,';');
int id=mapp[ta];
ans.num=d[id].num;
ans.id=id;
for(int i=1;i<=ans.num;i++)
for(int j=0;j<res.size();j++)
{
int k=find_c(res[j],h[id].col);
ans.a[j]=k;
ans.c[i].push_back(d[id].c[i][k]);
}
return ans;
}
data se2(const string&s)
{
data ans;
ans.num=0;
int p1=s.find("where ");
if(p1==string::npos) return se1(s);
string s1=s.substr(0,p1);
s1[p1-1]=';';
data t1=se1(s1);
int p2=s.find("in ");
string ss=s.substr(p1+6,p2-7-p1);
int k=find_c(ss,h[t1.id].col);
string s2=s.substr(p2+3);
data t2=se2(s2);
for(int i=1;i<=t1.num;i++)
for(int j=1;j<=t2.num;j++)
if(d[t1.id].c[i][k]==t2.c[j][0])
{
ans.num++;
ans.c[ans.num]=t1.c[i];
break;
}
return ans;
}
int main()
{
string s;
while(getline(cin,s))
{
if(s[0]=='c') creat(s);
else if(s[0]=='i') inser(s);
else if(s[0]=='s'&&s.find(" where ")==string::npos)
{
data t=se1(s);
m_print(t);
}
else
{
data t=se2(s);
m_print(t);
}
}
return 0;
}