逆波兰(非与或)表达式原理及C++代码实现
2024-09-05 04:32:21
p.p1 { margin: 0; font: 11px Menlo; color: rgba(209, 47, 27, 1); background-color: rgba(255, 255, 255, 1) }
运算符表达式:(a||b)||(c)&&d
分析语法
1 String16 analyzeData(const uint16_t* str, int &i)
2 {
3 int temp = i++;
4 while(!((str[i] == C16('&') && str[i+1] == C16('&'))
5 || (str[i] == C16('|') && str[i+1] == C16('|'))
6 || (str[i] == C16('!') && str[i+1] == C16('!'))
7 || str[i] == C16('(') || str[i] == C16(')') || str[i] == C16('\0'))) {
8 i++;
9 }
10 return dice::String16(str+temp,i-temp);
11 }
12
13 bool isCalChar(const uint16_t key,const uint16_t nextKey)
14 {
15 if((key == C16('&') && nextKey == C16('&'))
16 || (key == C16('|') && nextKey == C16('|'))
17 || (key == C16('!') && nextKey == C16('!'))
18 || key == C16('(') || key == C16(')')) {
19 return true;
20 }
21 return false;
22 }
23
24 vector<CustomMap> analyzeData(const uint16_t* keyword) {
25 int i = 0;
26 String16 data;
27 /* 存放运算符表达式的栈 */
28 sgi::stack<uint16_t> operChar;
29 /* 存放后缀表达式 */
30 vector<CustomMap> customDataList;
31 /* 判断输入的中缀表达式是否合法 */
32 {
33 /* 将中缀表达式转换为后缀表达式 */
34 for(i = 0; keyword[i] != '\0'; i++) {
35 /* 如果该字符为数字,解析该数字，并压入栈 */
36 if(isCalChar(keyword[i],keyword[i+1]) != true) {
37 data = analyzeData(keyword,i);
38 dice::CustomMap customMap;
39 customMap.customName = data;
40 customMap.operatorType = OperatorTypeNone;
41 customMap.customCode = 0l;
42 customDataList.push_back(customMap);
43 i--;
44 }
45 else if(keyword[i] == C16('(')) {
46 operChar.push(keyword[i]);
47 }
48 else if(keyword[i] == C16(')')) {
49 uint16_t operTemp[2] = {0};
50
51 operTemp[0] = operChar.top();
52
53 while(operTemp[0] != C16('(')) {
54 String16 strtemp(operTemp);
55 dice::CustomMap customMap;
56 customMap.customName = operTemp;//运算符
57 switch (operTemp[0]) {
58 case C16('!'):
59 customMap.operatorType = OperatorTypeDifference;
60 break;
61 case C16('&'):
62 customMap.operatorType = OperatorTypeIntersect;
63 break;
64 case C16('|'):
65 customMap.operatorType = OperatorTypeUnite;
66 break;
67 default:
68 break;
69 }
70 customMap.customCode = 0l;
71 customDataList.push_back(customMap);
72 operChar.pop();
73 operTemp[0] = operChar.top();
74 }
75 operChar.pop();
76 }
77 else if((keyword[i] == C16('&') &&keyword[i+1] == C16('&'))
78 || (keyword[i] == C16('|')&&keyword[i+1] == C16('|'))
79 || (keyword[i] == C16('!') && keyword[i+1] == C16('!'))
80 ) {
81 uint16_t operTemp[2] = {0};
82 /* 全部出栈，但是碰到 '('就要停止出栈 */
83 while(operChar.size() != 0) {
84 operTemp[0] = operChar.top();
85 if(operTemp[0] == C16('(')) {
86 break;
87 }
88 operChar.pop();
89 dice::CustomMap customMap;
90 customMap.customName = operTemp;//运算符
91 switch (operTemp[0]) {
92 case C16('!'):
93 customMap.operatorType = OperatorTypeDifference;
94 break;
95 case C16('&'):
96 customMap.operatorType = OperatorTypeIntersect;
97 break;
98 case C16('|'):
99 customMap.operatorType = OperatorTypeUnite;
100 break;
101 default:
102 break;
103 }
104 customMap.customCode = 0l;
105 customDataList.push_back(customMap);
106 }
107 /*将当前的表达式符号入栈*/
108 operChar.push(keyword[i]);
109 i++;
110 }
111 }
112 /* 存放表达式的栈可能还有数据 */
113 while (!operChar.empty()) {
114 uint16_t operTemp[2] = {0};
115 operTemp[0] = operChar.top();
116 operChar.pop();
117
118 dice::CustomMap customMap;
119 customMap.customName = operTemp;//运算符
120 switch (operTemp[0]) {
121 case C16('!'):
122 customMap.operatorType = OperatorTypeDifference;
123 break;
124 case C16('&'):
125 customMap.operatorType = OperatorTypeIntersect;
126 break;
127 case C16('|'):
128 customMap.operatorType = OperatorTypeUnite;
129 break;
130 default:
131 break;
132 }
133 customMap.customCode = 0l;
134 customDataList.push_back(customMap);
135 }
136 }
137 // 输出表达式代码
138 // vector<CustomMap>::iterator it;
139 //
140 // String16 strTemp;
141 // for(it = customDataList.begin(); it != customDataList.end(); it++) {
142 // dice::CustomMap customMap = (*it);
143 // strTemp = (*it).customName;
144 // printf("operatorType = %d\n",customMap.operatorType);
145 // api_print(strTemp.c_str());
146 // }
147 return customDataList;
148 }
解析处理数据
1 void getCustomIndexData(SearchDataAccessorIndex* indexDataAccessor, int32_t cityId, const vector<CustomMap>& cutomMapList, sgi::vector<int32_t>& poiIdxArray, int32_t& poiIdxCount) {
2
3 int32_t* loadIndexArray = NULL;
4 int32_t loadIndexCnt = 0u;
5 SearchStatus loadStatus = SearchStatusFailed;
6 SearchStatus returnStatus = SearchStatusFailed;
7 stack<CustomIdxData*> customStakData;
8 CustomIdxData* customIdxData1;
9 CustomIdxData* customIdxData2;
10 assert(indexDataAccessor);
11 vector<CustomMap>::iterator it;
12 CustomMap* cutomMap;
13 do {
14 poiIdxArray.clear();
15 poiIdxCount = 0;
16 returnStatus = SearchStatusSucceed;
17 for(it = cutomMapList.begin(); it != cutomMapList.end(); it++) {
18 cutomMap = it;
19 switch (cutomMap->operatorType) {
20 case OperatorTypeNone:
21 /* 获取单充电桩索引 */
22 loadStatus = indexDataAccessor->getPoiIdxListByCustomCode(cityId, cutomMap->customCode, (const int32_t*&)loadIndexArray, loadIndexCnt);
23 if (loadStatus == SearchStatusSucceed || loadStatus ==SearchStatusNoData) {
24 CustomIdxData* customIdxData = new CustomIdxData();
25 customIdxData->poiIdxArray.resize(loadIndexCnt);
26 customIdxData->poiIdxArray.assign(loadIndexArray, loadIndexArray + loadIndexCnt);
27 customIdxData->poiIdxCount = loadIndexCnt;
28 customStakData.push(customIdxData);
29 } else {
30 returnStatus = SearchStatusFailed;
31 }
32 break;
33 case OperatorTypeIntersect: /* 交集 */
34 customIdxData1 = customStakData.top();
35 customStakData.pop();
36 customIdxData2 = customStakData.top();
37 customStakData.pop();
38 customIdxData1->poiIdxCount = sgi::set_intersection(customIdxData1->poiIdxArray.begin(), customIdxData1->poiIdxArray.begin() + customIdxData1->poiIdxCount,
39 customIdxData2->poiIdxArray.begin(), customIdxData2->poiIdxArray.begin() + customIdxData2->poiIdxCount,
40 customIdxData1->poiIdxArray.begin()) - customIdxData1->poiIdxArray.begin();
41 delete customIdxData2;
42 customStakData.push(customIdxData1);
43 break;
44 case OperatorTypeUnite: /* 并集 */
45 {
46 customIdxData1 = customStakData.top();
47 customStakData.pop();
48 customIdxData2 = customStakData.top();
49 customStakData.pop();
50 CustomIdxData* customUniteIdxData= new CustomIdxData();
51 customUniteIdxData->poiIdxArray.resize(customIdxData1->poiIdxCount + customIdxData2->poiIdxCount);
52 customUniteIdxData->poiIdxCount = sgi::set_union(customIdxData1->poiIdxArray.begin(), customIdxData1->poiIdxArray.begin() + customIdxData1->poiIdxCount,
53 customIdxData2->poiIdxArray.begin(), customIdxData2->poiIdxArray.begin() + customIdxData2->poiIdxCount,
54 customUniteIdxData->poiIdxArray.begin()) - customUniteIdxData->poiIdxArray.begin();
55 delete customIdxData1;
56 delete customIdxData2;
57 customStakData.push(customUniteIdxData);
58 }
59 break;
60 case OperatorTypeDifference: /* 差集 */
61 customIdxData1 = customStakData.top();
62 customStakData.pop();
63 customIdxData2 = customStakData.top();
64 customStakData.pop();
65 customIdxData1->poiIdxCount = sgi::set_difference(customIdxData1->poiIdxArray.begin(), customIdxData1->poiIdxArray.begin() + customIdxData1->poiIdxCount,
66 customIdxData2->poiIdxArray.begin(), customIdxData2->poiIdxArray.begin() + customIdxData2->poiIdxCount,
67 customIdxData1->poiIdxArray.begin()) - customIdxData1->poiIdxArray.begin();
68 delete customIdxData2;
69 customStakData.push(customIdxData1);
70 break;
71 default:
72 returnStatus = SearchStatusFailed;
73 break;
74 }
75
76 if (returnStatus != SearchStatusSucceed) {
77 break;
78 }
79 }
80 if (returnStatus != SearchStatusSucceed) {
81 break;
82 }
83 customIdxData1 = customStakData.top();
84 customStakData.pop();
85 poiIdxCount = customIdxData1->poiIdxCount;
86 if ( poiIdxCount > 0) {
87 poiIdxArray.swap(customIdxData1->poiIdxArray);
88 }
89 delete customIdxData1;
90 if (poiIdxCount <= 0) {
91 returnStatus = SearchStatusNoData;
92 break;
93 }
94 } while (0);
95
96 return(returnStatus);
97 }
最新文章
- 使用IdleTest进行TDD单元测试驱动开发演练（3） 之 ASP.NET MVC
- PHP性能监测的工具介绍 - XHProf
- 关于使用jacob出现的异常
- 记一次linux服务器问题处理过程
- jquery插件lazyload.js延迟加载图片的使用方法
- codeforces A. Vasily the Bear and Triangle 解题报告
- 表生成器@ TableGenerator
- Java中的String与常量池[转帖]
- tomcat http 文件下载
- sqlServer将多字段设为主键方法
- VS2012 无法启动IIS Express Web服务器的解决方案
- HTML1网页三部份内容
- C++四种类型的转换
- SQL Server 服务器磁盘测试之SQLIO篇
- BootstrapTable，选中某几行，获取其数据并进行后台处理。以及其他的属性使用。
- python模块_多重继承的MRO
- Elasticsearch利用cat api快速查看集群状态、内存、磁盘使用情况
- 完整性约束&外键变种三种关系&数据的增删改
- Unix环境高级编程(六)进程控制
- C#之通过图片地址下载图片