表达式的解析

  1 #pragma once
  2 #include <string>
  3 #include <functional>
  4 #include <type_traits>
  5 #include <stack>
  6 struct OpratorObject
  7 {
  8     OpratorObject(int a)
  9     {
 10 
 11     }
 12     OpratorObject(double a)
 13     {
 14 
 15     }
 16     OpratorObject()
 17     {
 18 
 19     }
 20 };
 21 enum ExpType {
 22     ADD,    //加
 23     SUB,    //减
 24     MULT,        //乘
 25     DIV,        //除
 26     VALUE,        //直接取值
 27     FUNC
 28 };
 29 struct ExpNode
 30 {
 31     //每一个表达式都有值
 32     virtual    std::string GetValue() = 0;
 33 };
 34 struct ExpNodeString : public ExpNode
 35 {
 36 public:
 37     ExpType t;
 38     ExpNodeString* left;
 39     ExpNodeString* right;
 40     std::string val;
 41     std::string GetValue()
 42     {
 43         if (t == VALUE)
 44         {
 45             return val;
 46         }
 47         std::string lval = left->t == VALUE ? left->val : left->GetValue();
 48         std::string rval = right->t == VALUE ? right->val : right->GetValue();
 49         if (t == ADD)
 50         {
 51             return std::to_string(std::stof(lval) + std::stof(rval));
 52         }
 53         if (t == SUB)
 54         {
 55             return std::to_string(std::stof(lval) - std::stof(rval));
 56         }
 57         if (t == MULT)
 58         {
 59             return std::to_string(std::stof(lval) * std::stof(rval));
 60         }
 61         if (t == DIV)
 62         {
 63             return std::to_string(std::stof(lval) / std::stof(rval));
 64         }
 65 
 66         return "";
 67     }
 68 };
 69 struct ExpNodeStringValFunc : public ExpNodeString
 70 {
 71 public:
 72     std::string result;    //结果
 73     std::function<std::string(void)> func;
 74     std::string exp;
 75 };
 76 
 77 std::string right;    //
 78 struct Exp
 79 {
 80     //我目前先声明了一个node然后先放入左操作数，遇到（才创建新的子node
 81     //这里应该是遇到操作符 也要创建新的node
 82 
 83 
 84     static bool Parse(std::string s, ExpNodeString*& root)
 85     {
 86         root = new ExpNodeString();
 87         ExpNodeString* pCur = root;
 88         std::stack<ExpNodeString*> pCurStack;
 89         pCurStack.push(root);
 90         bool bLeft = true;    //先从左操作数开始
 91         for (int i = 0; i < s.size(); i++)
 92         {
 93             pCur = pCurStack.top();
 94             char ch = s[i];
 95             if (ch != ' ')
 96             {
 97                 if (isdigit(ch))
 98                 {
 99                     if (bLeft)
100                     {
101                         if (pCur->left == nullptr)
102                         {
103                             pCur->left = new ExpNodeString();
104                         }
105                         pCur->left->t = VALUE;
106                         pCur->left->val.push_back(ch);
107                     }
108                     else {
109                         if (pCur->right == nullptr)
110                         {
111                             pCur->right = new ExpNodeString();
112                         }
113                         pCur->right->t = VALUE;
114                         pCur->right->val.push_back(ch);
115                     }
116                 }
117                 else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
118                 {
119                     if (bLeft)
120                     {
121                         bLeft = false;
122                     }
123                     if (pCur->left != nullptr && pCur->right != nullptr)
124                     {
125                         ExpNodeString* pTemp = new ExpNodeString();
126                         //pCur->right = new ExpNodeString();
127                         pTemp->left = pCur;
128                         pCurStack.pop();
129                         pCurStack.push(pTemp);
130                         pCur = pCurStack.top();
131                     }
132                     //左子节点如果为空就不需要创建新的node了实际情况：（5+2）/3
133                     //if (pCur->left != nullptr)
134                     //{
135                     //    ExpNodeString* pTemp = new ExpNodeString();
136                     //    pTemp->left = pCur;
137                     //    pCurStack.pop();
138                     //    pCurStack.push(pTemp);
139                     //    //pCurStack.push(pTemp->left);
140                     //    if (pCur == root)
141                     //    {
142                     //        root = pTemp;
143                     //    }
144                     //    pCur = pTemp;
145                     //    pCur = pCurStack.top();
146                     //}
147                     //bLeft = false;
148 
149                     if (ch == '+')
150                     {
151                         pCur->t = ADD;
152                     }
153                     else    if (ch == '-')
154                     {
155                         pCur->t = SUB;
156                     }
157                     else    if (ch == '*')
158                     {
159                         pCur->t = MULT;
160                     }
161                     else    if (ch == '/')
162                     {
163                         pCur->t = DIV;
164                     }
165                 }
166                 else if (ch == '(')
167                 {
168                     //if (root == pCur) continue;
169                     if (bLeft)
170                     {
171                         pCur->left = new ExpNodeString();
172                         pCurStack.push(pCur->left);
173                         pCur = pCur->left;
174                     }
175                     else
176                     {
177                         pCur->right = new ExpNodeString();
178                         pCurStack.push(pCur->right);
179                     }
180                     bLeft = true;
181                 }
182                 else if (ch == ')')
183                 {
184                     pCur = pCurStack.top();
185                     //这里要一直弹出
186                     while (pCur->left != nullptr && pCur->right != nullptr)
187                     {
188                         pCurStack.pop();
189                         if (pCurStack.size() == 0)
190                         {
191                             ExpNodeString* pTemp = new ExpNodeString();
192                             pTemp->left = pCur;
193                             pCurStack.push(pTemp);
194                             root = pTemp;
195                         }
196                         pCur = pCurStack.top();
197                     }
198                     pCur = pCurStack.top();
199                     //}
200 
201                     //if (root == pCur)
202                     //{
203                     //    //小括号开头的
204                     //    ExpNodeString* pTemp = new ExpNodeString();
205                     //    pTemp->left = pCur;
206                     //    pCurStack.pop();
207                     //    pCurStack.push(pTemp);
208 
209                     //    //pCur = pCur->left;
210                     //    root = pTemp;
211                     //}
212                     bLeft = !bLeft;
213                 }
214             }
215         }
216         if (pCurStack.size() == 0 || pCurStack.size() == 1)
217         {
218             if (pCurStack.size() == 1)
219             {
220                 root = pCurStack.top();
221                 if (root->t != VALUE && root->left != nullptr && root->right != nullptr)
222                 {
223 
224                 }
225                 else {
226                     root = root->left;
227                 }
228             }
229             return true;
230         }
231         return false;
232     }
233     static bool Parse2(std::string s, ExpNodeString*& root)
234     {
235         //这里的思路是先组装一个left操作数，然后遇到operator然后在组装一个父节点
236         //中间遇到小括号出问题了
237         root = new ExpNodeString();
238         ExpNodeString* pCur = root;
239         std::stack<ExpNodeString*> pCurStack;
240         pCurStack.push(root);
241         bool bLeft = true;    //先从左操作数开始
242         for (int i = 0; i < s.size(); i++)
243         {
244             pCur = pCurStack.top();
245             char ch = s[i];
246             if (ch != ' ')
247             {
248                 if (isdigit(ch))
249                 {
250                     if (pCur->left == nullptr && pCur->right == nullptr)
251                     {
252                         pCur->t = VALUE;
253                         pCur->val.push_back(ch);
254                     }
255                     else
256                         if (bLeft == true)
257                         {
258                             pCur->left->t = VALUE;
259                             pCur->left->val.push_back(ch);
260                         }
261                         else
262                         {
263                             pCur->right->t = VALUE;
264                             pCur->right->val.push_back(ch);
265                         }
266                     /*if (pCur->left == nullptr)
267                     {
268                         pCur->left = new ExpNodeString();
269                     }
270 
271                     /*}
272                     else {
273                         if (pCur->right == nullptr)
274                         {
275                             pCur->right = new ExpNodeString();
276                         }
277                         pCur->right->t = VALUE;
278                         pCur->right->val.push_back(ch);
279                     }*/
280                 }
281                 else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
282                 {
283 
284                     //if (bLeft)
285                     //{
286                     //    bLeft = false;
287                     //}
288                     //else {
289                     //    //左子节点如果为空就不需要创建新的node了实际情况：（5+2）/3
290                     //    if (pCur->left != nullptr)
291                     //    {
292 
293                     ExpNodeString* pTemp = new ExpNodeString();
294                     ExpNodeString* pTempRight = new ExpNodeString();
295                     /*    if (root == pCur)
296                         {
297                             pTemp->left = pCur;
298                             pCurStack.pop();
299                             pCurStack.push(pTemp);
300                             pCurStack.push(pTemp->right);
301                         }
302                         else {*/
303                     pCurStack.pop();
304                     if (pCurStack.size() == 0)
305                     {
306                         pTemp->left = pCur;
307                         root = pTemp;
308                     }
309                     else
310                         pTemp->left = pCurStack.top();
311                     pTemp->right = pTempRight;
312                     pCurStack.push(pTemp);
313                     bLeft = false;
314                     //pCurStack.push(pTemp->left);
315                 /*    if (pCur == root)
316                     {*/
317 
318                     //}
319                     pCur = pTemp;
320                     //    }
321                     //    bLeft = false;
322                     if (ch == '+')
323                     {
324                         pCur->t = ADD;
325                     }
326                     else    if (ch == '-')
327                     {
328                         pCur->t = SUB;
329                     }
330                     else    if (ch == '*')
331                     {
332                         pCur->t = MULT;
333                     }
334                     else    if (ch == '/')
335                     {
336                         pCur->t = DIV;
337                     }
338                 }
339                 if (ch == '(')
340                 {
341                     if (!bLeft)
342                     {
343                         //if (root != pCur)
344                         {
345                             //pCur->right = new ExpNodeString();
346                             pCurStack.push(pCur->right);
347                             pCur = pCur->right;
348                             /*pCur->right = new ExpNodeString();
349                             pCur->left = new ExpNodeString();*/
350                             bLeft = true;
351                         }
352                     }
353                 }
354                 if (ch == ')')
355                 {
356                     pCurStack.pop();
357                     //同时意味着这个exp结束
358                 }
359             }
360         }
361         if (pCurStack.size() == 0 || pCurStack.size() == 1)
362         {
363             return true;
364         }
365         return false;
366     }
367     static bool Parse3(std::string s, ExpNodeString* pRoot)
368     {
369         // value operator
370         // func
371         // val
372         //
373     }
374 
375 };
以上是自己的思路，但是作用有限，有括号这一块，优先级不能有限判定，其次只支持最基本的+ - * /。
其中linq 有用到类似的思想。所以这里对其做了简单的实现，有现成的开源第三方库：Muparser.使用c++实现的，更完美的异常捕获，以及更强大的表达式解析。