九、表達式求值（1）

文章目錄

• 九、表達式求值（1）
• • 題目描述
  • 解題思路
  • 上機代碼

題目描述

背景：

我們的教材中已經介紹了表達式求值的算法，現在我們將該算法的功能進行擴展，要求可以處理的運算符包括：+、-、*、/、%（整數取余）、^（乘方）、（、）。

要求：

采用算符優先算法，計算的中間結果只保留整數。

輸入：

第一行為整數N。表示下面有N個表達式

從第二行起的后面N行為N個由整數構成的表達式

輸出：

共N行，每行為相應表達式的計算結果。

如果判斷出表達式有錯誤，則輸出：error.

如果在計算過程中出現除數為0的情況，則輸出：Divide 0.

特殊情況說明：

在表達式中，如果操作數出現負數（例如-8），則要特別注意。例如：
10加-8表示為：10±8。
10減-8表示為：10–8。

測試輸入期待的輸出時間限制內存限制額外進程

測試用例 1	4 2^3 2^0 2^3^2 2^(3-1)^(10-8)	8 1 512 16	1秒	64M	0
測試用例 2	11 (2+8 2+8) 8/0 8/(8+5-13) 2^(2-5) 10-(80-30(/3*3+4 10-80-30)/3*3+4 (2+8)(3+2) (2)3(8) 30(/3+3)+4 10(20-8)+2	error. error. Divide 0. Divide 0. error. error. error. error. error. error. error.	1秒	64M	0
測試用例 3	2 10(10) 14*10-(10)2	error. error.	1秒	64M	0
測試用例 4	14 18-32 18/4 18%3 10+20*4 10-20/4 (18-3)*3 10*(10) (10+2)/(8-10) (2*3)/(5*2) 10-(80-30)/3*3+4 (((2+8)*2-(2+4)/2)*2-8)*2 (((8+2)*(4/2))) 10/0 (10-80*2	-14 4 0 90 5 45 100 -6 0 -34 52 20 Divide 0. error.	1秒	64M	0

解題思路

算符優先算法的思路不管是在PPT還是教材中已經給出了詳細說明，我們再回顧一下

從左向右掃描表達式：

• 遇操作數，保存；
• 遇運算符號 ${\theta }_j$，與剛處理過的運算符 ${\theta }_i$ 比較：
  • 若 ${\theta }_i<{\theta }_j$ 則保存 ${\theta }_j$（已存入棧中的運算符的優先關系為 ${\theta }_1<{\theta }_2<{\theta }_3$···）
  • 若 ${\theta }_i>{\theta }_j$ 則說明 ${\theta }_i$ 是已掃描過的運算符中優先級最高的，可進行運算
  • 若 ${\theta }_i={\theta }_j$ 則說明括號內算式已算完，需消去括號

算符優先算法用兩個工作棧：OPTR棧保存運算符；一個是OPND棧保存操作數或運算結果。

基本思想

1.將操作數棧置空，表達式起始符“#”入棧（運算符棧的棧底元素）。

2.依次讀入表達式中的每一項(有完整意義)，若是操作數，則進OPND棧；若是運算符，則與OPTR棧的棧頂運算符比較優先級后作相應操作， 直至表達式求值完畢（即OPTR棧頂元素和當前讀入字符均為“#”）

Tips：

老師上課時認真講了這個算法，并預留了這個算法關于 C 語言實現的代碼，相信細心的同學已經注意到了。但是這段代碼是不能直接通過這個題的，有一些小的 bug 需要我們進行處理。因此我們可以選擇理解代碼的邏輯，針對具體 bug 進行訂正即可。

上機代碼

#include<stdlib.h> #include<stdio.h> #include<string.h> #include<math.h> #define Nul 0x00char chinput[200], *p; /* 運算式存儲字符串,運算式當前讀取位置 */ int operationgFlag=0; /* operationgFlag=1時意味著出現除數為0的情況 */struct t /* 符號棧 */ {char dat[200];int top; }prt;struct d /* 數字棧 */ {long int dat[200];int top; }prd;char PRI[9][9]= /* 優先級表 */ {{'>','>','<','<','<','<','<','>','>'},{'>','>','<','<','<','<','<','>','>'},{'>','>','>','>','<','<','<','>','>'},{'>','>','>','>','<','<','<','>','>'},{'>','>','>','>','>','<','<','>','>'},{'>','>','>','>','>','<','<','>','>'},{'<','<','<','<','<','<','<','=',Nul},{'>','>','>','>','>','>',Nul,'>','>'},{'<','<','<','<','<','<','<',Nul,'='} };void pushd( long int a ) /* 數字入棧 */ {prd.dat[ prd.top++ ]=a; } void pusht( char a ) /* 符號入棧 */ {prt.dat[ prt.top++ ]=a; } long int popd( ) /* 數字出棧 */ {return prd.dat[ --prd.top ]; } char popt( ) /* 符號出棧 */ {return prt.dat[ --prt.top ]; }long int numble() /* 數字整理 */ {long int b=0;do{ b = b*10 + *p -'0'; // 組成整數p++;}while ( *p>='0' && *p<='9' ) ;return b; }long operation( long int x, long int y, char a ) {switch( a ){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y ) return x/y;else { printf("Divide 0.\n"); operationgFlag=1; return 0;}case '%': return ((long int) fmod(x,y));case '^': if (y>=0 ) return pow(x,y);else { printf("error.\n"); operationgFlag=1; return 0;}} }int signswitch( char a ) /* 符號轉換 */ {switch( a ){ case '+': return 0; case '-': return 1;case '*': return 2; case '/': return 3;case '%': return 4; case '^': return 5;case '(': return 6; case ')': return 7;case '#': return 8;} }char refusal( char a,char b ) /* 判定優先級 */ {return PRI[signswitch(a)][signswitch(b)]; }int main() {int i,j,n,k,l, flag=0; /* flag=0前一個符號不是) */scanf("%d",&n);while(n--){//初始化operationgFlag = 0;flag = 0;char b;prt.dat[0] = '#';prt.top = 1;prd.top = 0;scanf("%s", chinput); /* 接收運算式 */strcat ( chinput, "#"); /* 在運算式結尾加#號 */p = chinput;while ( *p!='#' || prt.dat[prt.top-1]!='#' ) //表達式中還有值或者棧中還有值{if ( *p>='0' && *p<='9') { j = numble(); /* 如果是數字進行整理并入棧 */pushd( j );}else /* 如果是符號與棧頂的符號比較并運算 */{if ( flag==1 && *p=='(' ){printf("error.\n");goto h;}else if ( *p==')') flag = 1;else flag = 0;switch ( refusal(prt.dat[prt.top-1], *p ) ){case '<': pusht ( *p++ ); break; /* 高則入棧 */case '=': popt( ); /* 脫括號 */p++; break;case '>': b = popt(); /* 低則進行棧頂計算 */k = popd(); /* 第二操作數出棧 */l = popd(); /* 第一操作數出棧 */k = operation(l,k,b); /* 計算 */if(operationgFlag==1)goto h;else{pushd(k); break; /* 計算結果入棧 */}case Nul: printf("error.\n");goto h;}}}if(prd.top-1 == 0) //數字棧中只有一個數，那就是最終結果printf("%d\n",prd.dat[prd.top-1]); /* 輸出 */elseprintf("error.\n");h:; /* 繼續下一個 *//*有三處需要直接進入下一次循環，goto不失是個好方法*/}return 0; }

總結

以上是生活随笔為你收集整理的九、表达式求值（1）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。