怎么解析一个数学表达式

fly3ds

回复 20# cokeboL

* / + -的都加进去了 现在要搞搞优先级

   

fly3ds

回复 21# fly3ds


已经可以识别并计算浮点数!  

-bash-4.1$ ./expre
12 + 3 - 4 / 5 * 2.1 + 5
12 + 3 - 4 / 5 * 2.1 + 5

12 + 3 - 4 / 10.500000 + 5

12 + 3 - 0.380952 + 5

15 - 0.380952 + 5

15 - 5.380952
9.619048
-bash-4.1$

井蛙夏虫

回复 8# w_anthony
我好像记得是后缀表达式，也就是逆波兰表示法。碰到操作数的时候压入堆栈，碰到操作符的时候处理。

   

w_anthony

回复 23# 井蛙夏虫


    你说的方法听起来挺靠谱的，我其实也记不清到底是哪种了，毕竟大学课本上的东西。
虽然前缀和后缀都可以解决这个问题，但是大学的时候应该不会深入讲递归，我想应该是你说的这个方法。

lxyscls

直接参考Louden的《编译原理与实践》
第四章有个现成的caculator，基本可以解决你的问题
用的是递归下降，就是不能处理浮点数

井蛙夏虫

回复 24# w_anthony
我也是在大学时学数据结构看到的这种方法。编译原理时就是说LL这些方法了。
如果会lex和yacc的话就简单的多，只需要写词法规则和语法规则，不需要自己解析了。


   

w_anthony

今天上班没什么事，无聊写了个，测试运行了下，效果不错。
方法是解析生成一颗与运算优先级相关的树，然后前缀递归计算结果。

代码BUG了，先编辑下。
现在修改过了，应该没问题了……

再优化一下，去掉了while，因为这个while的次数是可预见的。

1. #include <stdio.h>
   
2. 
   
3. enum ElemType
   
4. {
   
5.         Type_Number = 0,
   
6.         Type_Root,
   
7.         Type_Plus,
   
8.         Type_Subtract,
   
9.         Type_Prior,
   
10.         Type_Multiply,
    
11.         Type_Divide,
    
12. };
    
13. 
    
14. class CCalcElem
    
15. {
    
16. public:
    
17.         CCalcElem() : m_iType(Type_Number) {}
    
18.         ~CCalcElem()
    
19.         {
    
20.                 if (m_iType != Type_Number)
    
21.                 {
    
22.                         delete m_lpLeft;
    
23.                         delete m_lpRight;
    
24.                 }
    
25.         }
    
26. protected:
    
27.         CCalcElem(const CCalcElem&) {}
    
28.         const CCalcElem& operator=(const CCalcElem&) { return *this; }
    
29. public:
    
30.         int m_iType;
    
31.         union {
    
32.                 double m_dlNumber;
    
33.                 struct {
    
34.                         CCalcElem* m_lpLeft;
    
35.                         CCalcElem* m_lpRight;
    
36.                 };
    
37.         };
    
38.         CCalcElem* m_lpParent;
    
39. };
    
40. 
    
41. static bool IsBlank(char ch)
    
42. {
    
43.         return ((ch == ' ') || (ch == '\t') || (ch == '\r') || (ch == '\n'));
    
44. }
    
45. 
    
46. int AnalyseNumber(const char*& lpExpress, CCalcElem* lpTree);
    
47. 
    
48. static int AnalyseOperator(const char*& lpExpress, CCalcElem* lpTree)
    
49. {
    
50.         while (IsBlank(*lpExpress))
    
51.                 ++lpExpress;
    
52.         int iType;
    
53.         switch (*lpExpress)
    
54.         {
    
55.         case '+':
    
56.                 iType = Type_Plus;
    
57.                 break;
    
58.         case '-':
    
59.                 iType = Type_Subtract;
    
60.                 break;
    
61.         case '*':
    
62.                 iType = Type_Multiply;
    
63.                 break;
    
64.         case '/':
    
65.                 iType = Type_Divide;
    
66.                 break;
    
67.         case ')':
    
68.                 ++lpExpress;
    
69.                 return 1;
    
70.         case '\0':
    
71.                 return 0;
    
72.         default:
    
73.                 return -1;
    
74.         }
    
75.         ++lpExpress;
    
76.         CCalcElem* lpNode = lpTree->m_lpParent;
    
77.         if (iType < Type_Prior)
    
78.         {
    
79.                 if (lpNode->m_iType != Type_Root)
    
80.                 {
    
81.                         lpNode = lpNode->m_lpParent;
    
82.                         if (lpNode->m_iType != Type_Root)
    
83.                                 lpNode = lpNode->m_lpParent;
    
84.                 }
    
85.         }
    
86.         else
    
87.         {
    
88.                 if ((lpNode->m_iType != Type_Root) && (lpNode->m_iType > Type_Prior))
    
89.                         lpNode = lpNode->m_lpParent;
    
90.         }
    
91.         CCalcElem* const lpElem = new CCalcElem;
    
92.         lpElem->m_lpParent = lpNode;
    
93.         CCalcElem* const lpNodeRight = lpNode->m_lpRight;
    
94.         lpNode->m_lpRight = lpElem;
    
95.         lpElem->m_iType = iType;
    
96.         lpElem->m_lpLeft = lpNodeRight;
    
97.         lpElem->m_lpRight = NULL;
    
98.         return AnalyseNumber(lpExpress, lpElem);
    
99. }
    
100. 
     
101. int AnalyseNumber(const char*& lpExpress, CCalcElem* lpTree)
     
102. {
     
103.         while (IsBlank(*lpExpress))
     
104.                 ++lpExpress;
     
105.         if (*lpExpress == '(')
     
106.         {
     
107.                 ++lpExpress;
     
108.                 const int iType = lpTree->m_iType;
     
109.                 lpTree->m_iType = Type_Root;
     
110.                 const int iResult = AnalyseNumber(lpExpress, lpTree);
     
111.                 if (iResult > 0)
     
112.                 {
     
113.                         lpTree->m_iType = iType;
     
114.                         return AnalyseOperator(lpExpress, lpTree->m_lpRight);
     
115.                 }
     
116.         }
     
117.         else
     
118.         {
     
119.                 double dl;
     
120.                 int count;
     
121.                 if (sscanf(lpExpress, "%lf%n", &dl, &count) > 0)
     
122.                 {
     
123.                         lpTree->m_lpRight = new CCalcElem;
     
124.                         lpTree->m_lpRight->m_lpParent = lpTree;
     
125.                         lpTree->m_lpRight->m_dlNumber = dl;
     
126.                         lpExpress += count;
     
127.                         return AnalyseOperator(lpExpress, lpTree->m_lpRight);
     
128.                 }
     
129.         }
     
130.         return -1;
     
131. }
     
132. 
     
133. static double CalcTree(CCalcElem* lpTree)
     
134. {
     
135.         if (lpTree->m_iType != Type_Number)
     
136.         {
     
137.                 const double dlLeft = CalcTree(lpTree->m_lpLeft);
     
138.                 const double dlRight = CalcTree(lpTree->m_lpRight);
     
139.                 const int iType = lpTree->m_iType;
     
140.                 if (iType == Type_Plus)
     
141.                         return (dlLeft + dlRight);
     
142.                 else if (iType == Type_Subtract)
     
143.                         return (dlLeft - dlRight);
     
144.                 else if (iType == Type_Multiply)
     
145.                         return (dlLeft * dlRight);
     
146.                 else
     
147.                         return (dlLeft / dlRight);
     
148.         }
     
149.         return lpTree->m_dlNumber;
     
150. }
     
151. 
     
152. static bool AnalyseExpress(const char* lpExpress, double& dlValue)
     
153. {
     
154.         CCalcElem nElem;
     
155.         nElem.m_iType = Type_Root;
     
156.         nElem.m_lpLeft = NULL;
     
157.         nElem.m_lpRight = NULL;
     
158.         if (AnalyseNumber(lpExpress, &nElem) == 0)
     
159.         {
     
160.                 dlValue = CalcTree(nElem.m_lpRight);
     
161.                 return true;
     
162.         }
     
163.         return false;
     
164. }
     
165. 
     
166. int main(int, char**)
     
167. {
     
168.         printf("%s", "Input expression:");
     
169.         char str[512];
     
170.         gets(str);
     
171.         double dlResult;
     
172.         if (AnalyseExpress(str, dlResult))
     
173.                 printf("%s = %lf\r\n", str, dlResult);
     
174.         else
     
175.                 printf("%s", "Invalid expression!\r\n");
     
176.         return 0;
     
177. }
     

复制代码

yulihua49

fly3ds 发表于 2013-10-18 20:11
https://github.com/fly3ds/linux_test

有兴趣看看这里面的expre.c，还是没有完成，不过照这个思路编下去 ...

用stptok去分割操作符：
rp=stptok(arg->cp,p,
                        sizeof(arg->argbuf)-(p-arg->argbuf),",+*-/%()#;");
这是我的计算器里的代码，这里不处理=，它在外部处理。
要处理：#注释，；结束。
函数执行完，判断*rp是哪个操作符即可。

stptok()可以在网上搜到，有源码。

w_anthony

fly3ds 发表于 2013-10-20 11:41
已经可以识别并计算浮点数!  

-bash-4.1$ ./expre
12 + 3 - 4 / 5 * 2.1 + 5
12 + 3 - 4 / 5 * 2.1 + 5

12 + 3 - 4 / 10.500000 + 5

12 + 3 - 0.380952 + 5

15 - 0.380952 + 5

15 - 5.380952
9.619048
-bash-4.1$

你不觉得第一步应该先算/，再算*么？

fly3ds

回复 29# w_anthony

这是常见的处理方式，不过我看不是必需的。