表達式求值

表達式求值問題

①問題描述

表達式是數據運算的基本形式。人們的書寫習慣是中綴式，如：11+22*(7-4)/3。中綴式的計算按運算符的優先級及括號優先的原則，相同級別從左到右進行計算。表達式還有后綴式（如：22 7 4 - * 3 / 11 +）和前綴式（如：+ 11 / * 22 – 7 4 3）。后綴表達式和前綴表達式中沒有括號，給計算帶來方便。如后綴式計算時按運算符出現的先后進行計算。本設計的主要任務是進行表達式形式的轉換及不同形式的表達式計算。

②基本要求

l? 從文件或鍵盤讀入中綴表達式。

l? 設計操作數為多位整數，操作符為加、減、乘、除、求模的中綴表達式求值算法。

l? 設計將中綴表達式轉換為后綴表達式的算法。

l? 設計將中綴表達式轉換為前綴表達式的算法。

l? 設計后綴表達式求值算法。

l? 設計前綴表達式求值算法。

l? 輸出各種形式的表達式。

③設計要點提示

l? 算數表達式的計算往往是通過棧來實現的。

l? 讀入或掃描表達式的同時，完成運算符和操作數的識別處理。

l? 識別操作數時，注意將其字符序列轉換成整數（如：‘15’→15）或實數（如：‘15.4’ →15.4）形式進行存儲。

l? 可以將表達式轉換成一棵二叉樹，通過先序、中序、后序遍歷得到前綴、中綴、后綴表達式。

l? 仿表1來構建測試用例。

表1 表達式計算測試用例示例

測試項目	測試用例	預期結果
基本測試	3	3
	1+2*3-4/2	5
	11+22	33
	1+22*(5-3)/4	12
	(((2)))-3	-1
	…	?
容錯測試	1+2（	表達式出錯提示
	2/0	表達式出錯提示
	2%0	表達式出錯提示
	(2-4)^ù3.1	表達式出錯提示
	2+3)(-5	表達式出錯提示
	(((2))-3	表達式出錯提示
	2.5%2	表達式出錯提示
	1+++1	表達式出錯提示
	2 2	表達式出錯提示
	1#1	表達式出錯提示
	…	表達式出錯提示

  1 #include <iostream>
  2 #include<string.h>
  3 #include<ctype.h>
  4 #include<malloc.h> /* malloc()等 */
  5 #include<limits.h> /* INT_MAX等 */
  6 #include<stdio.h> /* EOF(=^Z或F6),NULL */
  7 #include<stdlib.h> /* atoi() */
  8 #include<io.h> /* eof() */
  9 #include<math.h> /* floor(),ceil(),abs() */
 10 #include<process.h> /* exit() */
 11 /* 函數結果狀態代碼 */
 12 #define TRUE 1
 13 #define FALSE 0
 14 #define OK 1
 15 #define ERROR 0
 16 #define INFEASIBLE -1
 17 #define OVERFLOW 3
 18 /* #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 */
 19 typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
 20 typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */
 21 using namespace std;
 22 typedef char SElemType;
 23 #define STACK_INIT_SIZE 100 //存儲空間初始分配量
 24 #define STACKINCREMENT 10//存儲空間分配增量
 25 
 26 
 27 /*——————————————————————————棧的操作——————————————————————————*/
 28 typedef struct{
 29    SElemType * base;//在棧構造之前和銷毀之后，base的值為NULL
 30    SElemType * top;//棧頂指針
 31    int stacksize;
 32 }SqStack;
 33 Status InitStack(SqStack &S)
 34 {//構造一個空棧
 35     S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 36     if(!S.base) exit(OVERFLOW);
 37     S.top=S.base;
 38     S.stacksize=STACK_INIT_SIZE;
 39     return OK;
 40 }
 41 Status DestroyStack(SqStack &S)
 42 {//銷毀棧
 43     free(S.base);
 44     S.top=NULL;
 45     S.base=NULL;
 46     S.stacksize=0;
 47     return OK;
 48 }
 49 
 50 Status StackEmpty(SqStack S)
 51 {
 52     if(S.top==S.base) return TRUE;
 53     else return FALSE;
 54 }
 55 int StackLength(SqStack S)
 56 {
 57     return S.top-S.base;
 58 }
 59 Status GetTop(SqStack S,SElemType &e)
 60 {
 61     if(S.top>S.base)
 62         {e=*(S.top-1);return OK;}
 63     else return ERROR;
 64 }
 65 Status Push(SqStack &S,SElemType e)
 66 {
 67     if(S.top-S.base==S.stacksize)//若棧滿，追加存儲空間
 68     {
 69         S.base=(SElemType *) realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
 70         if(!S.base) exit(OVERFLOW);//存儲內存分配失敗
 71         S.top=S.base+S.stacksize;
 72         S.stacksize += STACKINCREMENT;
 73     }
 74     *(S.top)=e;//可直接使用 *S.top++=e；
 75     S.top++;
 76     return OK;
 77 }
 78 
 79 Status Pop(SqStack &S,SElemType &e)
 80 {
 81     if(S.top==S.base)
 82     {
 83         cout<<"表達式錯誤，溢出！！"<<endl;
 84         exit(OVERFLOW);
 85     }
 86     e=*--S.top;
 87     return OK;
 88 }
 89 Status StackTraverse(SqStack S, void(* visit)(SElemType))
 90 {
 91     while(S.top>S.base)
 92         visit(*S.base++);
 93     printf("\n");
 94     return OK;
 95 }
 96 
 97 
 98 //表達式求值
 99 char Precede(SElemType c1,SElemType c2)//判斷c1,c2的優先關系,棧頂元素是c1，如果要入棧的元素c2優先權小（>），
100                                        //則彈出c1進行運算,再把c2繼續嘗試入棧,c1棧底，c2入棧運算符
101 {
102     char f;
103     switch(c2)
104     {
105         case '.' : f='<';
106                    break;
107         case '+' :
108         case '-' : if(c1=='('||c1=='\n') f='<';
109                    else f='>';
110                    break;
111 
112         case '*' :
113         case '/' : if(c1=='*'||c1=='/'||c1==')') f='>';
114                    else f='<';
115                    break;
116         case '(' : if(c1==')')
117                     {
118                         printf("括號輸入不合法！");
119                         exit(ERROR);
120                     }
121                    else f='<';
122                    break;
123         case ')' : switch(c1)
124                     {
125                     case '\n':
126                               printf("缺乏左括號！");
127                               exit(ERROR);
128                     case '(': f='=';
129                               break;
130                     default : f='>';
131                     }
132                     break;
133         case '\n' : switch(c1)
134                    {
135                      case '\n': f='=';
136                                 break;
137                     case '(':
138                         printf("缺少右括號！");
139                         exit(ERROR);
140                     default : f='>';
141                    }
142     }
143     return f;
144 }
145 Status In(SElemType c)
146 { // 判斷c是否為7種運算符之一
147     switch(c)
148     {
149         case '.' :
150         case '+' :
151         case '-' :
152         case '*' :
153         case '/' :
154         case '(' :
155         case ')' :
156         case '\n' :return TRUE;
157         default  :return FALSE;
158     }
159 }
160 SElemType Operate(SElemType a,SElemType theta,SElemType b)
161 { // 做四則運算a theta b，返回運算結果
162     switch(theta)
163     {
164         case '+':return a+b;
165         case '-':return a-b;
166         case '*':return a*b;
167         case '.':return a;
168     }
169     if(b!=0)  return a/b;
170     else
171     {
172         cout<<"分母不能為0！"<<endl;
173         exit(OVERFLOW);
174     }
175 }
176 SElemType EvaluateExpression(SElemType M[100])
177 {//算術表達式求值的算符優先算法。設OPTR和OPND分別為運算符棧和運算數棧。
178  //OP為運算符集合
179     SqStack OPTR,OPND;
180     SElemType a,b,c,x;
181     int m=0,n=0;
182     InitStack(OPTR); Push(OPTR,'\n');
183     InitStack(OPND);
184 
185     GetTop(OPTR,x);
186 
187     int i=1;
188 
189     while(M[i]!='\n' || x!='\n')//當運算符棧棧頂元素為‘\n’，并且此時'\n'嘗試入棧時,作為表達式結束的標志
190     {
191 
192         if(M[i]>='0'&&M[i]<='9') // M[i]是操作數
193         {
194             while(M[i]>='0'&&M[i]<='9')
195             {m=m*10+(M[i]-'0');i++;}
196             Push(OPND,m); // 將該操作數的值(不是ASCII碼)壓入運算數棧OPND
197             m=0;
198 
199         }
200         else if(In(M[i]))   // M[i]是運算符
201          switch(Precede(x,M[i]))
202         {
203           case '<': //棧頂優先權低,進棧
204             Push(OPTR,M[i]);i++;
205             break;
206           case '=': //脫括號并接受下一字符
207             Pop(OPTR,x);i++;
208             break;
209           case '>': //退棧并將運算結果入棧,不再getchar，將當前字符繼續嘗試壓棧
210             Pop(OPTR,x);
211             Pop(OPND,a);
212             Pop(OPND,b);
213             Push(OPND,Operate(b,x,a));
214             break;
215         }
216 
217       else // c是非法字符
218       {
219         printf("出現非法字符\n");
220         exit(ERROR);
221       }
222 
223       GetTop(OPTR,x); // 將運算符棧OPTR的棧頂元素賦給x
224     }
225     Pop(OPND,x);
226 
227     if(!StackEmpty(OPND)) // 運算數棧OPND不空(運算符棧OPTR僅剩′\n′ )
228         {
229             printf("表達式不正確\n");
230             exit(ERROR);
231         }
232 
233     return x;
234 }
235 
236 Status InToPost(SElemType M[100])
237 {
238     SqStack OPTR,OPND;
239     SElemType a,b,c,x;
240     int m=0,n=0;
241     InitStack(OPTR); Push(OPTR,'\n');
242     InitStack(OPND);
243     GetTop(OPTR,x);
244     int i=1;
245     while(M[i]!='\n' || x!='\n')//當運算符棧棧頂元素為‘\n’，并且此時'\n'嘗試入棧時,作為表達式結束的標志
246     {
247 
248         if(M[i]>='0'&&M[i]<='9') // M[i]是操作數
249         {
250             while(M[i]>='0'&&M[i]<='9')
251             {m=m*10+(M[i]-'0');i++;}
252             Push(OPND,m); // 將該操作數的值(不是ASCII碼)壓入運算數棧OPND
253             cout<<m;
254             m=0;
255 
256         }
257         else if(In(M[i]))   // M[i]是運算符
258          switch(Precede(x,M[i]))
259         {
260           case '<': //棧頂優先權低,進棧
261             Push(OPTR,M[i]);i++;
262             break;
263           case '=': //脫括號并接受下一字符
264             Pop(OPTR,x);i++;
265             break;
266           case '>': //退棧并將運算結果入棧,不再getchar，將當前字符繼續嘗試壓棧
267             Pop(OPTR,x);cout<<x;
268             Pop(OPND,a);
269             Pop(OPND,b);
270             Push(OPND,Operate(b,x,a));
271             break;
272         }
273 
274       else // c是非法字符
275       {
276         printf("出現非法字符\n");
277         exit(ERROR);
278       }
279 
280       GetTop(OPTR,x); // 將運算符棧OPTR的棧頂元素賦給x
281     }
282     Pop(OPND,x);
283 
284     if(!StackEmpty(OPND)) // 運算數棧OPND不空(運算符棧OPTR僅剩′\n′ )
285         {
286             printf("表達式不正確\n");
287             exit(ERROR);
288         }
289 
290     return OK;
291 }
292 int ArrayLength(SElemType M[100])
293 {//求數組的長度，不包含'\n'
294     int j=1;
295     while(M[j]!='\n')
296     {
297         j++;
298     }
299     return j-1;
300 }
301 
302 Status InToPre(SElemType M[100])
303 {//中綴表達式轉前綴
304     SqStack OPTR,RESULT;
305     SElemType a,b,c,x;
306     int m=0,n=0;
307     InitStack(OPTR); Push(OPTR,'\n');
308     InitStack(RESULT);
309     GetTop(OPTR,x);
310     int i=ArrayLength(M);
311     while(M[i]!='\n')//當運算符棧棧頂元素為‘\n’作為表達式結束的標志
312     {
313 
314         if(M[i]>='0'&&M[i]<='9') // M[i]是操作數，直接壓入RESULT棧
315         {
316             int j=0;
317             while(M[i]>='0'&&M[i]<='9')
318             {m+=pow(10,j)*M[i];i--;}
319 
320             Push(RESULT,m); // 將該操作數的值(不是ASCII碼)壓入結果棧RESULT
321             m=0;
322 
323         }
324         else if(M[i]==')')//假如是右括號，直接將它壓棧。
325         {
326             Push(OPTR,M[i]);
327             i--;
328         }
329         else if(M[i]=='(')//假如是左括號，棧中運算符逐個出棧并壓入RESULT棧，直到遇到右括號。右括號出棧并丟棄。
330         {
331                 while(x!=')')
332                 {
333                     Pop(OPTR,x);Push(RESULT,x);
334                     GetTop(OPTR,x);
335                 }
336                 Pop(OPTR,x);//將OPTR中的')'彈出
337                 i--;
338         }
339         else if(In(M[i]))   // M[i]是其它運算符
340          switch(Precede(x,M[i]))
341         {
342           case '<': //棧頂優先權低,進棧
343             Push(OPTR,M[i]);i--;
344             break;
345           case '=': //脫括號并接受下一字符
346             Pop(OPTR,x);i--;
347             break;
348           case '>': //運算符較棧頂算符優先級低，彈出OPTR棧中算符，并存入RESULT棧，直至遇到優先級相等的算符或棧為空為止，然后將當前算符存入OPTR棧
349             if(x==')')
350             {
351                 Push(OPTR,M[i]);
352             }
353             else
354             {
355               while(Precede(x,M[i])=='>'&&StackLength(OPTR)>1)
356               {
357                   if(x==')') break;//如果遇到右括號退出循環
358                   else {Pop(OPTR,x);Push(RESULT,x); GetTop(OPTR,x);}
359               }
360               Push(OPTR,M[i]);
361 
362             }
363             i--;
364             break;
365          }
366 
367       else // c是非法字符
368       {
369         printf("出現非法字符\n");
370         exit(ERROR);
371       }
372       GetTop(OPTR,x); // 將運算符棧OPTR的棧頂元素賦給x
373     }
374 
375     while(StackLength(OPTR)>1) // 運算數棧OPND不空(運算符棧OPTR僅剩′\n′ )
376         {
377             Pop(OPTR,x);Push(RESULT,x);
378         }
379     while(StackLength(RESULT)>1)
380     {
381         Pop(RESULT,x);cout<<x;
382     }
383     GetTop(RESULT,x);cout<<x;
384     return OK;
385 }
386 
387 SElemType PostExpression(SElemType M[100])
388 {//算術表達式求值的算符優先算法。設OPTR和OPND分別為運算符棧和運算數棧。
389  //OP為運算符集合
390     SqStack OPND;
391     SElemType a,b,c,x;
392     int m=0,n=0;
393     InitStack(OPND);
394     int i=1;
395     while(M[i]!='\n')//當運算符棧棧頂元素為‘\n’,作為表達式結束的標志
396     {
397 
398         if(M[i]>='0'&&M[i]<='9') // M[i]是操作數
399         {
400             m=M[i]-'0';
401             Push(OPND,m); // 將該操作數的值(不是ASCII碼)壓入運算數棧OPND
402             i++;
403         }
404         else if(In(M[i]))   // M[i]是運算符
405          {
406             Pop(OPND,a);
407             Pop(OPND,b);
408             Push(OPND,Operate(b,M[i],a));
409             i++;
410          }
411 
412       else // c是非法字符
413       {
414         printf("出現非法字符\n");
415         exit(ERROR);
416       }
417     }
418     Pop(OPND,x);
419     return x;
420 }
421 
422 SElemType PreExpression(SElemType M[100])
423 {//算術表達式求值的算符優先算法。設OPTR和OPND分別為運算符棧和運算數棧。
424  //OP為運算符集合
425     SqStack OPND;
426     SElemType a,b,c,x;
427     int m=0,n=0;
428     InitStack(OPND);
429     int i=ArrayLength(M);
430     while(M[i]!='\n')//當運算符棧棧頂元素為‘\n’,作為表達式結束的標志
431     {
432 
433         if(M[i]>='0'&&M[i]<='9') // M[i]是操作數
434         {
435             m=M[i]-'0';
436             Push(OPND,m); // 將該操作數的值(不是ASCII碼)壓入運算數棧OPND
437             i--;
438         }
439         else if(In(M[i]))   // M[i]是運算符
440          {
441             Pop(OPND,a);
442             Pop(OPND,b);
443             Push(OPND,Operate(a,M[i],b));
444             i--;
445          }
446 
447       else // c是非法字符
448       {
449         printf("出現非法字符\n");
450         exit(ERROR);
451       }
452     }
453     Pop(OPND,x);
454     return x;
455 }
456 
457 int main()
458 {
459     system("color 70");
460     //表達式求值
461     printf("———————————表達式求值———————————");
462     cout<<endl;
463     char c;
464     printf("請輸入算術表達式:\n");
465     SElemType M[100];
466     M[0]='\n';
467     c=getchar();
468     int j=1;
469     while(c!='\n')
470     {
471         M[j]=c;
472         c=getchar();
473         j++;
474     }
475     M[j]='\n';
476     int a=EvaluateExpression(M);//強制轉換成int型
477     cout<<"運算結果為："<<endl;
478     printf("%d\n",a); // 返回值(8位二進制，1個字節)按整型格式輸出
479 
480 
481 
482     printf("———————————表達式轉換———————————");
483     cout<<endl;
484     char c2;
485     printf("請輸入算術表達式:\n");
486     SElemType M2[100];
487     M2[0]='\n';
488     c2=getchar();
489     int j1=1;
490     while(c2!='\n')
491     {
492         M2[j1]=c2;
493         c2=getchar();
494         j1++;
495     }
496     M2[j1]='\n';
497     printf("中綴表達式為：\n");
498     int i=1;
499     while(M2[i]!='\n')
500     {
501         if((M2[i]!='(')&&(M2[i]!=')')) {cout<<M2[i];i++;}
502         else i++;
503     }
504     cout<<endl;
505     printf("后綴表達式為：\n");
506     InToPost(M2);
507     cout<<endl;
508     cout<<"前綴表達式為："<<endl;
509     InToPre(M2);
510     cout<<endl;
511 
512 
513     cout<<"——————————后綴表達式求值——————————"<<endl;
514     cout<<"請輸入后綴表達式："<<endl;
515     char c3;
516     SElemType M3[100];
517     M3[0]='\n';
518     c3=getchar();
519     int j3=1;
520     while(c3!='\n')
521     {
522         M3[j3]=c3;
523         c3=getchar();
524         j3++;
525     }
526     M3[j3]='\n';
527     int a3=PostExpression(M3);
528     cout<<"運算結果為："<<endl;
529     printf("%d\n",a3);
530 
531     cout<<"——————————前綴表達式求值——————————"<<endl;
532     cout<<"請輸入前綴表達式："<<endl;
533     char c4;
534     SElemType M4[100];
535     M4[0]='\n';
536     c4=getchar();
537     int j4=1;
538     while(c4!='\n')
539     {
540         M4[j4]=c4;
541         c4=getchar();
542         j4++;
543     }
544     M4[j4]='\n';
545     int a4=PreExpression(M4);
546     cout<<"運算結果為："<<endl;
547     printf("%d\n",a4);
548     return 0;
549 }