算術(shù)表達式求值

1、題目：算術(shù)表達式求值問題內(nèi)容：一個算術(shù)表達式是由操作數(shù) (operand) 、運算符 (operator) 和界限符 (delimiter) 組成的。假設(shè)操作數(shù)是正整數(shù)，運算符只含加減乘除等四種運算符， 界限符有左右括號和表達式起始、結(jié)束符“ #”，如： #( 7+15) * ( 23-28/4 ) #。引入表達式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達式的值。要求：(1)從鍵盤讀入一個合法的算術(shù)表達式，輸出正確的結(jié)果。( 2 )顯示輸入序列和棧的變化過程。選作內(nèi)容：操作數(shù)類型擴充到實數(shù)。一：問題分析和任務(wù)定義1. 問題分析：分析題目并參考書目可以基本了解完成一個算術(shù)表達式所存

2、在的問題。對一個表達式來說， 由于各種運算符和界限符的運用， 運算符和界限符的優(yōu)先級決定了算術(shù)表達式不是簡單的從左往右的運算。因此設(shè)計算法完成算術(shù)表達式時就要考慮各運算符和界限符的優(yōu)先級， 同時還要注意操作數(shù)與算符的判斷。 在算法中要求完成操作數(shù)、 運算符和界限符的出入棧， 運算符和界限符的優(yōu)先級比較和操作數(shù)之間的運算。 最后完成的算法要求輸入一個算術(shù)表達式， 能夠正確的計算出來它的最后結(jié)果并輸出。 為了不用考慮算符優(yōu)先級， 將輸入的中 綴表達式轉(zhuǎn)換成后綴表達式。這樣就可以知道實現(xiàn)本程序需要進行的操作：1) 建立空棧，存儲信息；2) 運用函數(shù)實現(xiàn)出入棧和取棧頂元素操作。3) 將中綴表達式轉(zhuǎn)換成

3、后綴表達式。4) 實現(xiàn)后綴表達式的求解。5) 建立一個函數(shù)使中綴表達式能夠被有效輸入。本程序的關(guān)鍵是中綴表達式轉(zhuǎn)換成后綴表達式對于棧的操作( 1 )建空棧setStack() 運算的結(jié)果是將棧頂元素返回。 ( 2 )清空棧EmptyStack () ，可以用于判斷棧內(nèi)元素的有無，在棧頂元素的輸出被使用。 ( 3)入棧 push (),出棧pop()和取棧頂元素top()。 2. 任務(wù)定義 1) 本演示程序中，利用棧將輸入的中綴表達式轉(zhuǎn)換成后綴表達式，并完成其求解過程來 達到計算表達式的目的。 2) 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示" 提示信息 "

4、之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，以“回車符”為結(jié)束標(biāo)志。相應(yīng)的輸 入數(shù)據(jù)和運算結(jié)果顯示在其后。 3) 程序執(zhí)行的命令包括： 1)輸入任意一個整數(shù)表達式； 2)是否繼續(xù)。 4) 測試數(shù)據(jù) 輸入一個整數(shù)表達式： 3+ ( 5*8-9 ) 輸出： 后綴表達式： 3 5 8 *9 -+ 結(jié)果為：34繼續(xù)？(y/n )二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計 算術(shù)表達式中各數(shù)據(jù)元素間存在一種線性關(guān)系，設(shè)計的數(shù)據(jù)類型如下：#define MAXNUM 50typedef int DataType;typedef struct DataType sMAXNUM;int t;SeqStack,*PSeq

5、Stack;/ 定義一個類型名為SeqStack 的數(shù)據(jù)類型本算法設(shè)計過程中只采用加減乘除等四種運算符， 題目要求借助棧完成算法設(shè)計， 提示中要把中綴表達式轉(zhuǎn)換成后綴表達式計算，因此操作運算包括要建空棧、清空棧、進棧、出棧、取棧頂元素，中綴表達式轉(zhuǎn)換成后綴表達式，后綴表達式的運算等。將運算符和界限符一起描述為算符，本程序的設(shè)計如下：( 1 )先定義一下數(shù)據(jù)結(jié)構(gòu)來存儲算術(shù)表達式。( 2)建空棧setstack(),清空棧。( 3 )對棧進行的運算函數(shù)，出入棧和取棧頂元素。( 4 )中綴表達式轉(zhuǎn)換成后綴表達式的函數(shù)its() 。( 5 )后綴表達式計算函數(shù)。( 6 )設(shè)計存放后綴表達式的隊列。(

6、7)主函數(shù)main(),使得整個程序完整進行。三、詳細設(shè)計和編碼為了實現(xiàn)概要設(shè)計中的所有數(shù)據(jù)類型，對每個操作給出算法。對主程序和其他模塊也都需要寫出算法。1 ) 數(shù)據(jù)類型#define MAXNUM 50typedef int DataType;typedef struct DataType sMAXNUM;int t;SeqStack,*PSeqStack;/ 定義一個類型名為 SeqStack 的數(shù)據(jù)類型建空棧和其它關(guān)于棧的操作這部分為棧的運算問題。為后面表達式轉(zhuǎn)換和計算做準(zhǔn)備。這方面的知識書上有系統(tǒng)講到，不需要過多去設(shè)計算法。2 ) 表達式的轉(zhuǎn)換和計算將中綴表達式轉(zhuǎn)換成后綴表達式， 順序

7、掃描中綴算術(shù)表達式， 當(dāng)讀到數(shù)字時直接將起送至輸出隊列中； 當(dāng)讀到運算符時， 將棧中所有優(yōu)先級高于或等于該運算符的運算符彈出， 送至輸出隊列中，再將當(dāng)前運算符入棧；當(dāng)讀入左括號時，即入棧；當(dāng)讀入右括號時，將靠近棧的第一個左括號上面的運算符依次彈出， 送至輸出隊列中， 再刪除棧中左括號。 在計算后綴表達式式，最后保存的值是最先取出參與運算，所以要用到棧。讀到數(shù)字時直接送至輸出隊列中：switch(c1) case '0':case '1':case '2':case '3':case '4':case '5&

8、#39;:case '6':case '7':case '8':case '9':set =1;suffixj+=c1; /* 遇到數(shù)字輸出 */break;當(dāng)讀到左括號時入棧：case '(':set=0;push(ps, c1); /* 遇到左括號，入棧*/break;當(dāng)讀入右括號時，將靠近棧的第一個左括號上面的運算符依次彈出，送至輸出隊列中，再刪除棧中左括號：case ')':c2 = ')' /* 遇到右括號把右括號賦值給c2*/while(!EmptyStack(ps) /

9、* 當(dāng)棧不為空時*/c2=top(ps); /* 遇到右括號取棧頂*/pop(ps); /* 出棧 */if(c2 ='(')break; /*遇到左括號時停止出棧*/suffixj+=c2; /*c2 的值放入后綴表達式中 */當(dāng)讀到加減乘除號時，棧和后綴表達式的變化。因為優(yōu)先級的關(guān)系，將加減號同時考慮，乘除號同時考慮。讀到加減號處理時運用算法如下：case '+':case '-':while(!EmptyStack(ps) /* 當(dāng)棧不為空時*/c2 = top(ps); /* 將棧頂元素賦值給c2*/if(c2 ='+'|

10、 c2 ='-'| c2 = '*' | c2 = '/') pop(ps); /* 遇到加減號時棧中棧頂元素是加減乘除四種運算符出棧*/suffixj+ = c2; /* 將 c2 放入后綴表達式中 */else if(c2='(')break; /* 遇到加減號時棧頂元素是左括號不進行出棧*/push(ps, c1); /*c1 入棧 */break;讀到乘除號處理時算法與加減法基本一致， 但在 if 語句時只需考慮c2 = '*' | c2 ='/'。計算后綴表達式時讀到數(shù)值時計算sum 的值

11、switch(c) case '0': case '1' case '2'case '3' case '4' case '5'case '6' case '7' case '8':case '9':if(set = 1) /* 遇到操作數(shù)*/sum = sum * 10 + c - '0' /*sum 的計算 */else /*所遇到的不是操作數(shù)*/sum = c - '0'/*sum 的計算 */ se

12、t=1;break;考慮遇到空格、制符表和運算符時sum 值的入棧情況case ' ': case't': case 'n':if (set = 1) push(ps, sum); /* 遇到空格或制表符sum 入棧 */set = 0; break;case '+': case case '*': case '/':if(set = 1) push(ps, sum); /* 遇到運算符時sum 入棧 */set = 0; 遇到加減乘除四個運算符時將棧頂和次棧頂元素分別運用所遇到運算符進行運算，并將

13、運算結(jié)果入棧num2 = top(ps); /* 棧頂元素賦值給num2*/pop(ps); /* 元素出棧 */if(EmptyStack(ps) /* 當(dāng)棧為空 */ free(ps); /* 釋放棧內(nèi)空間 */ return 0;num1 = top(ps); /* 棧頂元素賦值給num1*/pop(ps); /* 元素出棧 */if(c = '+') /*c 為加號時 */push(ps, num1 + num2); /*num1 與 num2 的和入棧 */if(c = '-') /*c 為減號時 */push(ps, num1 - num2); /*

14、num1 與 num2 的差入棧 */if(c = '*') /*c 為乘號時 */push(ps, num1 * num2); /*num1 與 num2 的積入棧 */if(c = '/') /*c 為除號時 */push(ps, num1 / num2); /*num1 與 num2 的商入棧 */break;default:free(ps);return 0; 該部分為程序的核心算法，即將算術(shù)表達式的值正確的輸出。4)主函數(shù)基本的數(shù)據(jù)定義，并實現(xiàn)表達式的輸入，并調(diào)用 getline() 函數(shù)void main() char c, infixMAXNUM,

15、 suffixMAXNUM;int result;int flag = 1;while(flag = 1) printf(" 請輸入任意一個整數(shù)算術(shù)表達式 :n");getline(infix, MAXNUM); /*調(diào)用 getline() 函數(shù) */if(its(infix, suffix) = 1) printf(" 所得后綴為 :%sn", suffix);else printf(" 無效綴 !n");調(diào)用 calculateSuffix() 函數(shù)使程序完整if(calculateSuffix(suffix, &res

16、ult) = 1) /* 調(diào)用 calculateSuffix() 函數(shù) */ printf(" 結(jié)果為 :%dn", result);else printf(" 非法后綴 !n");四、上機調(diào)試1.編程中遇到的幾個問題剛看到題目的時候，我對題意沒有理解，運用的普通的方法來完成程序，運行時輸入無括 號的算術(shù)表達式可以正確輸出結(jié)果，但輸入帶括號的表達式時輸出的結(jié)果與運算結(jié)果不符。 因此根據(jù)提示，設(shè)計算法將輸入的中綴表達式轉(zhuǎn)換成后綴表達式再運算得到結(jié)果。在此算法 即最終使用的程序中，中綴表達式轉(zhuǎn)換成后綴表達式函數(shù)中2、算法設(shè)計、調(diào)試的經(jīng)驗和體會剛開始拿到這個

17、問題時自己對如何設(shè)計算法沒有一點頭緒。但我從中理解了題目的意 思，也找到了解決問題的思路，最重要的是啟發(fā)了我運用本課程中所學(xué)的去解決該問題。我做完本次實驗還有一個體會是：設(shè)計一個程序需要按一個完整的步驟來進行。首先必須弄懂程序要解決的是什么問題。在弄懂之后大腦中就要開始構(gòu)思要用是什么方法來解決問題，多問同學(xué)、老師或者多查閱相關(guān)資料通過網(wǎng)絡(luò)等等。只有經(jīng)過這個過程才會提高自己的發(fā)現(xiàn)問題、分析問題、解決問題的能力，使得思維更加嚴(yán)謹(jǐn)。雖然這次課程設(shè)計不是很難，不是做 一個比較大的系統(tǒng)， 代碼不算多，但是我認為要成功地完成一個程序，包括完整的實驗報告都要投入必要的時間和精力，認真對待，這樣我們可以收獲不

18、少東西。通過這次課程設(shè)計， 我深知自己學(xué)習(xí)的知識還遠遠不夠。這是一種全面綜合訓(xùn)練， 是與課堂聽講，自學(xué)和練習(xí)相輔相成的，必不可少的一個教學(xué)環(huán)節(jié)。 這次的課程設(shè)計為以后的學(xué)習(xí)打下了堅實的基礎(chǔ)。我們網(wǎng)絡(luò)工程專業(yè)就要跟大量的程序算法打交道。這就要求我們必須將每一句語言的精髓領(lǐng)悟透徹，注重細節(jié)，掌握每一種算法的功能。只有這樣，我們在解決 實際生活中的問題的時候，才能運用的得心應(yīng)手，恰到好處。五、測試結(jié)果及其分析1、運行程序后，初界面：|話輸入任意一個整斷口-,表達式上d圖1 :運行程序后初界面2、輸入表達式后:(y/n)yXDebugXhiu. exe3、輸入y圖3:輸入y后4、再次輸入表達式:&qu

19、ot; I: VetJugX ghru, eze" 何離人任苣二未整數(shù)算木表三式t 忸福后綴對3 3 0*皓昊為二34 靖輸入任量一個整數(shù)算亦表達力E»3+4-<9-4/2)所得尼蜃為：5 3 *4 +S 4 2 / 隹果為：匕圖4:再次輸入表達式5、輸入n后:- x:XDebugX£hru.金工日圖5:輸入n后6、在初始界面后輸入#時:圖6:在初始界面后輸入#時六、用戶使用說明在輸入時候，必須為正確的表達式。否則程序?qū)⑴袛喑鲥e，提前結(jié)束程序。七、參考文獻1、王昆侖。數(shù)據(jù)結(jié)構(gòu)與算法。北京：中國鐵道出版社。 200 72、譚浩強。C程序設(shè)計(第三版)。北京：清

20、華大學(xué)出版社。20053、譚浩強。C程序設(shè)計指導(dǎo)。北京：清華大學(xué)出版社。2005八、附錄帶有注釋的源程序#include<stdio.h>#include<malloc.h>#define MAXNUM 50typedef int DataType;typedef struct DataType sMAXNUM;int t;SeqStack,*PSeqStack;/定義一個類型名為 SeqStack的數(shù)據(jù)類型/*構(gòu)造一個空棧*/PSeqStack setStack()PSeqStack stack;stack=(SeqStack*)malloc(sizeof( SeqS

21、tack);/ 強制轉(zhuǎn)換數(shù)據(jù)類型if (stack=NULL)printf(" 空間不夠 !n"); /elsestack->t=-1;return stack;返回空棧頂/* 清空棧 */int EmptyStack(PSeqStack stack)return stack->t=-1;/* 入棧 */void push(PSeqStack stack, DataType x)if (stack->t >= MAXNUM - 1) / 判斷棧滿printf(" 滿溢 !n");/棧滿時輸出“滿溢! ”elsestack->

22、t = stack->t+1;stack->sstack->t=x; / 棧未滿時元素入棧/* 出棧 */void pop(PSeqStack stack)if (stack->t=-1)printf(" 滿溢 !n"); / 當(dāng)?？諘r輸出“滿溢! ”elsestack->t = stack->t-1; / 當(dāng)棧不空時元素出棧/* 返回棧頂元素的值*/DataType top(PSeqStack stack)return stack->sstack->t; / 返回棧頂元素/* 將中綴表達式轉(zhuǎn)換為后綴表達式， 順利轉(zhuǎn)換返回 1

23、 ，若轉(zhuǎn)換過程中發(fā)現(xiàn)中綴表達式非法則返回 0*/int its(const char* infix, char* suffix)int set = 0; /*set 記錄狀態(tài)， 等于 1 表示剛讀入的是操作數(shù)， 等于 0表示剛讀入的是運算符，*/* 設(shè)置這個變量是為了在每輸出一個整數(shù)后輸出一個空格， 以免 連續(xù)輸出的兩個整數(shù)混在一起。 */char c1, c2;PSeqStack ps = setStack();int i, j = 0;for(i=0; infixi!='0'i+) /* 中綴表達式不為空時,遍歷表達式*/c1=infixi; /* 把遍歷到的元素指賦給c1

24、*/if(set= 1) suffixj+=' '/* 讀到數(shù)字時輸出一個空格 */ switch(c1) case ' ':case 't':case 'n':break; /* 遇到空格或制表符忽略*/case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9&

25、#39;:set =1;suffixj+=c1; /* 遇到數(shù)字輸出 */break;case '(':push(ps, c1); /* 遇到左括號，入棧*/break;case ')':c2 = ')' /* 遇到右括號把右括號賦值給c2*/while(!EmptyStack(ps) /* 當(dāng)棧不為空時*/c2=top(ps); /* 遇到右括號取棧頂*/pop(ps); /* 出棧 */if(c2 ='(')break; /*遇到左括號時停止出棧*/suffixj+=c2; /*c2 的值放入后綴表達式中 */if(c2 !=

26、'(') /*c2 不是左括號時*/free(ps); /* 釋放棧內(nèi)空間 */suffixj+='0'return 0;break;case '+': case '-':while(!EmptyStack(ps) /* 當(dāng)棧不為空時*/c2 = top(ps); /* 將棧頂元素賦值給c2*/if(c2 ='+'| c2 ='-'| c2 = '*' | c2 = '/') pop(ps); /* 遇到加減號時棧中棧頂元素是加減乘除四種運算符出棧suffixj+ =

27、 c2; /* 將 c2 放入后綴表達式中 */else if(c2='(')break; /* 遇到加減號時棧頂元素是左括號不進行出棧*/push(ps, c1); /*c1 入棧 */break;case '*':case '/':while(!EmptyStack(ps) /* 當(dāng)棧不為空時*/c2 = top(ps); /*將棧頂元素賦值給c2*/if(c2 = '*' | c2 = '/') pop(ps); /* 遇到乘除號時棧中棧頂元素是乘除運算符時出棧*/suffixj+ = c2; /* 將 c2

28、 放入后綴表達式中 */else if(c2='+'|c2='-'|c2='(')break; /* 遇到乘除號時棧中棧頂元素是加減號和左括號時不進行出棧*/*/push(ps, c1);break;default:free(ps); /* 釋放棧內(nèi)空間 */suffixj+ = '0'return 0; while(!EmptyStack(ps) /* 當(dāng)棧不為空*/c2 = top(ps); /* 棧頂元素賦值給c2*/pop(ps); /* 元素出棧 */if(c2 = '(') /*c2 值為左括號時*/f

29、ree(ps); /* 釋放棧內(nèi)空間 */suffixj+ = '0'return 1;suffixj+ = c2; /* 將 c2 值放入后綴表達式中 */ free(ps); /* 釋放棧內(nèi)空間 */suffixj+ = '0'return 1;/* 計算后綴表達式*/int calculateSuffix(const char * suffix, int * presult) int set = 0; /*set 記錄狀態(tài)， 等于 1 表示剛讀入的是操作數(shù)， 等于 0表示剛讀入的是運算符，*/PSeqStack ps = setStack();int su

30、m = 0, num1, num2; /* 定義 num1 、 num2 用于操作數(shù)間的運算，并定義數(shù)據(jù)sum*/int i;char c;for(i = 0; suffixi != '0' i+) /* 中綴表達式不為空時,遍歷表達式*/c = suffixi; /* 把遍歷到的元素指賦給c*/switch(c) case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7

31、9;:case '8':case '9':if(set = 1) /* 遇到操作數(shù)*/sum = sum * 10 + c - '0' /*sum 的計算 */else /*所遇到的不是操作數(shù) */sum = c - '0'/*sum 的計算 */set=1;break;case ' ':case't':case 'n':if (set = 1) push(ps, sum); /*遇到空格或制表符sum 入棧 */set = 0; break;case '+':cas

32、e '-':casecase '/':if(set = 1) push(ps, sum); /*遇到運算符時sum 入棧 */set = 0; if(EmptyStack(ps) /* 當(dāng)棧為空 */free(ps); /* 釋放棧內(nèi)空間 */return 0;num2 = top(ps); /* 棧頂元素賦值給num2*/pop(ps); /* 元素出棧 */if(EmptyStack(ps) /* 當(dāng)棧為空 */free(ps); /* 釋放棧內(nèi)空間 */return 0;num1 = top(ps); /* 棧頂元素賦值給num1*/pop(ps); /* 元素出棧 */if(c = '+') /*c 為加號時 */push(ps, num1 + num2); /*num1 與 num2 的和入棧 */ if(c = '-') /*c 為減號時 */push(ps, num1 - num2); /*num1 與 num2 的差入棧 */ if(c = '*') /*c 為乘號時 */push(ps, num1 * num2); /*num1 與 num2 的積入棧 */if(c = '/') /*c 為除號時 */push(ps, nu