在某宝上接到如下题
四、查询类任务
实现数据记录查询选择函数select, 该函数根据表达查询条件的字符串,对加载的数据进行查询。其结果包含两部分,一是符合条件的记录总数,以函数值的形式返回;二是符合条件的所有记录编号,存入通过形参传递而来的数组中。关于查询条件字符串,它类似编程语言的逻辑表达式的结构,其构成可包含:
1)表示关系运算的字符: “<”, “<=”, “>”, “>=”, “==”, “!=”;
2)表示逻辑运算的关键字:“AND”, “OR”, “NOT”;
3)可改变运算优先级别的小括号 " ()",若没有括号两类运算符的优先次序与C/C++中相应的保持一致;
4)字段名,表示对当前记录行指定字段值的引用,如 “Open >= 9.15” 表达的条件就是开盘价大于等于9.15;
5)为了简化,约定字段名在关系运算符的左边,标准格式下运算符前后各一个空格。
通过以上内容,可以灵活写出简单或复合的查询条件。比如 “Open >= 9.15 AND Date == 2017-1-3” 表达了查找2017年1月3日开盘价大于等于9.15的股票交易记录。其中,表达日期时,采取“年-月-日”短横线连接的固定格式。
提示:你需再设计一个解析查询条件字符串的方案,以判断一条记录是否符合需要。
函数的原型:int* Select(const char *condition, int& n); 其中:
1)condition 为查询的条件表达式,具体规则如上所述;
2)n为结果的数量,这里是以引用的形式传入。
3)返回值为整数类型的指针存放数据编号的数组,应考虑将它创建为一个动态数组空间,因为查询结果的具体数目事先不可预知。
给出了如下解决方式,非专修C/C++, 欢迎大佬们批评指正
之所以分享一下, 是因为客户对string类一无所知, 并且一定要用某种递归树去解决,让我改一下, 正巧我忙活半天在外放松休闲, 不想整。 我说,最终解布尔表达式的时候可以递归, 把“true” “false” 设为出口, 循环变递归不就好了吗。
我觉得这个解法真的易懂有木有<<<
看见这题我的第一反应是,后缀表达式, 好像还有个高级的名字
Share with you, Happy Day。
/**
--此处仅将 or and not 设为操作符 输出成 || && ! 正如not优先级较高
--将每个判断例: A>=1 用具体的那条记录过滤,即是判断该记录中的那个字段是否附合这个最小条件 输出 成一个true 或者 false
--即该表达式转为 一个关于true和false的布尔表达式
求解布尔表达式 判断该条记录是否符合
下面仅select函数为主要, 其他为测试数据
**/
#include<stdlib.h>
#include<iostream>
#include <sstream>
using namespace std;
class Record
{
// 为了避免字符串与double float long型 或者时间相关的转换,
// 所有字段全部用字串 比较时直接比较字典序 strcmp
// 此处若自行优化,建议保留字串和日期的字典序比较
public:
string Date;
string Open;
string High;
string Low;
string Close;
string Adj_Close;
string Volume;
string Code;
string Change;
string Pct_change;
string getValueByFieldName(string fieldName) {
if ("Date" == fieldName) {
return Date;
} else if ("Open" == fieldName) {
return Open;
} else if ("High" == fieldName) {
return High;
} else if ("Low" == fieldName) {
return Low;
} else if ("Close" == fieldName) {
return Close;
} else if ("Adj_Close" == fieldName) {
return Adj_Close;
} else if ("Volume" == fieldName) {
return Volume;
} else if ("Code" == fieldName) {
return Code;
} else if ("Change" == fieldName) {
return Change;
} else if ("Pct_change" == fieldName) {
return Pct_change;
}
}
};
/**
测试数据 DB
将100 条数据分为四类
**/
Record* init() {
Record *records = new Record[100];
for (int i = 0; i < 100; i++) {
if (i % 2) {
records[i].Date = "2018-12-22";
records[i].Open = "8.1";
records[i].High = "8.18";
records[i].Low = "8.09";
records[i].Close = "8.16";
records[i].Adj_Close = "8.028069";
records[i].Volume = "85984049";
records[i].Code = "000001.SZ";
records[i].Change = "8.06";
records[i].Pct_change = "8.0065934";
} else if (i % 3) {
records[i].Date = "2017-12-20";
records[i].Open = "7.1";
records[i].High = "7.18";
records[i].Low = "7.09";
records[i].Close = "7.16";
records[i].Adj_Close = "7.028069";
records[i].Volume = "75984049";
records[i].Code = "000001.SZ";
records[i].Change = "7.06";
records[i].Pct_change = "7.0065934";
} else if (i % 5) {
records[i].Date = "2016-12-20";
records[i].Open = "6.1";
records[i].High = "6.18";
records[i].Low = "6.09";
records[i].Close = "6.16";
records[i].Adj_Close = "6.028069";
records[i].Volume = "65984049";
records[i].Code = "000001.SZ";
records[i].Change = "6.06";
records[i].Pct_change = "6.0065934";
} else {
records[i].Date = "2015-12-12";
records[i].Open = "5.1";
records[i].High = "5.18";
records[i].Low = "5.09";
records[i].Close = "5.16";
records[i].Adj_Close = "5.028069";
records[i].Volume = "55984049";
records[i].Code = "000001.SZ";
records[i].Change = "5.06";
records[i].Pct_change = "5.0065934";
}
}
return records;
}
string getFieldStr(int n, string conditionStr) {
string front = conditionStr.substr(0, n);
string field = front.substr(front.find_last_of(" ") + 1, front.length());
int k=0;
if ((k = field.find_last_of('(')) != -1) {
field = field.substr(k + 1, field.length());
}
return field;
}
string getValueStr(int n, string conditionStr, int operLength) {
string end = conditionStr.substr(n + operLength, conditionStr.length());
string value = end.substr(0, end.find_first_of(" "));
int j=0;
if ((j = value.find_first_of(')')) != -1) {
value = value.substr(0, j);
}
return value;
}
string replaceResult(string conditionStr) {
string t1 = "true and true"; //1&&1 1
string t2 = "true and false"; //1&&0 0
string t3 = "false and true"; //0&&1 0
string t4 = "false and false"; //0&&0 0
string f1 = "true or true"; //1||1 1
string f2 = "true or false"; //1||0 1
string f3 = "false or true"; //0||1 1
string f4 = "false or false"; //0||0 0
string p5 = "(true)";
string p6 = "(false)";
string n1 = "not true";
string n2 = "not false";
string n3 = "not (true)";
string n4 = "not (false)";
string arrays[14] = {
n1,n2,n3,n4,t1, t2, t3, t4, f1, f2, f3, f4, p5, p6
};
for (int i=0; i<14; i++) {
string regx = arrays[i];
int n = -1;
if ((n = conditionStr.find(regx)) != -1) {
if ((regx == "not (true)") || (regx == "not true")) {
conditionStr = conditionStr.replace(n, regx.length(), "false");
break;
}
if ((regx == "not (false)") || (regx == "not false")) {
conditionStr = conditionStr.replace(n, regx.length(), "true");
break;
}
if (regx == "true and true") {
conditionStr = conditionStr.replace(n, regx.length(), "true");
break;
} else if(regx.find("and") != -1) {
conditionStr = conditionStr.replace(n, regx.length(), "false");
break;
}
if (regx == "false or false") {
conditionStr = conditionStr.replace(n, regx.length(), "false");
break;
} else if(regx.find("or") != -1) {
conditionStr = conditionStr.replace(n, regx.length(), "true");
break;
}
if (regx == "(true)") {
conditionStr = conditionStr.replace(n, regx.length(), "true");
break;
}
if (regx == "(false)") {
conditionStr = conditionStr.replace(n, regx.length(), "false");
break;
}
}
}
return conditionStr;
}
Record* Select(const char *condition, int& n) {
//按要求n 这个参数是获取的条数 定义结果为N的数组 索引为resultIndex 每次匹配成功加1
Record selectResults[n];
int resultIndex = 0;
// 在条件前后加入空格, 使开始和结束字符容易判断
string condition1 = condition;
string conditionStr = " " + condition1 + " ";
cout<<conditionStr<<endl;
// 备份原始串
string conditionStrTemp = conditionStr;
// A == 123
Record* records = init();
for (int i = 0; i < 100; i++) {
// 一条记录
Record item = records[i];
// 用表达式判断该条记录
conditionStr = conditionStrTemp;
while (true) {
// conditionStr
// "<", "<=", ">", ">=", "==", "!=";
// 使用 find_last_of 判断 是否存在 这些符号
bool isOver = true;
int n=-1;
if ((n = conditionStr.find("==")) != -1) {
// 判断一个字段
// 在这个位置将字符串拆成两半
// 前半段 字段 可能相邻 空格 找出 find_last_of
// 后半段 值 可能相邻 空格 找出 find_first_of
// 替换掉括号
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 2);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (value == resultValue) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 2;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
} else if ((n = conditionStr.find("!=")) != -1) {
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 2);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (value != resultValue) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 2;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
} else if ((n = conditionStr.find(">=")) != -1) {
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 2);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (resultValue >= value) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 2;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
} else if ((n = conditionStr.find("<=")) != -1) {
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 2);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (resultValue <= value) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 2;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
} else if ((n = conditionStr.find(">")) != -1) {
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 1);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (resultValue > value) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 1;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
} else if ((n = conditionStr.find("<")) != -1) {
string field = getFieldStr(n, conditionStr);
string value = getValueStr(n, conditionStr, 1);
string resultValue = item.getValueByFieldName(field);
string resultFlag = "false";
if (resultValue < value) {
resultFlag = "true";
}
int itemLength = field.length() + value.length() + 1;
conditionStr = conditionStr.replace(n - field.length(), itemLength, resultFlag);
isOver = false;
}
if (isOver) {
break;
}
}
stringstream ss;
ss<<i;
string s1 = ss.str();
string temp = conditionStr.substr(1, conditionStr.length()-2);
// 转化为boolean表达式之后, 计算该表达式的值
while(true) {
temp = replaceResult(temp);
if (temp.length() == 4 || temp.length() ==5) {
break;
}
}
if (temp == "true") {
// cout<<"记录" + s1 + "已命中"<<endl;
cout<<item.Date+","+ item.Open+","+ item.High+","+ item.Low+","+ item.Close+","+ item.Adj_Close+","+ item.Volume+","+ item.Code+","+ item.Change+","+ item.Pct_change<<endl;;
selectResults[resultIndex++] = item;
if (resultIndex == n) {
printf("已查询到限制%d条", n);
return selectResults;
}
}
}
printf("已查询到%d条", resultIndex);
return selectResults;
}
int main(void) {
// 记得not and or前后空格
// "<", "<=", ">", ">=", "==", "!=";不空格 括号不空格 谢谢
char condition[100] = "Date==2016-12-20";
int a=100;
Select(condition, a);
}
布尔表达式的求解, while(true), 以及里面的break, 应该是可以优化, 不过没关系了, 重在分享易懂的解决方式, 嘿