算術(shù)表達(dá)式求值

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

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

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

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

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

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

7、掃描中綴算術(shù)表達(dá)式， 當(dāng)讀到數(shù)字時(shí)直接將起送至輸出隊(duì)列中； 當(dāng)讀到運(yùn)算符時(shí)， 將棧中所有優(yōu)先級高于或等于該運(yùn)算符的運(yùn)算符彈出， 送至輸出隊(duì)列中，再將當(dāng)前運(yùn)算符入棧；當(dāng)讀入左括號時(shí)，即入棧；當(dāng)讀入右括號時(shí)，將靠近棧的第一個(gè)左括號上面的運(yùn)算符依次彈出， 送至輸出隊(duì)列中， 再刪除棧中左括號。 在計(jì)算后綴表達(dá)式式，最后保存的值是最先取出參與運(yùn)算，所以要用到棧。讀到數(shù)字時(shí)直接送至輸出隊(duì)列中：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)讀到左括號時(shí)入棧：case '(':set=0;push(ps, c1); /* 遇到左括號，入棧*/break;當(dāng)讀入右括號時(shí)，將靠近棧的第一個(gè)左括號上面的運(yùn)算符依次彈出，送至輸出隊(duì)列中，再刪除棧中左括號：case ')':c2 = ')' /* 遇到右括號把右括號賦值給c2*/while(!EmptyStack(ps) /

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

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

12、t=1;break;考慮遇到空格、制符表和運(yùn)算符時(shí)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); /* 遇到運(yùn)算符時(shí)sum 入棧 */set = 0; 遇到加減乘除四個(gè)運(yùn)算符時(shí)將棧頂和次棧頂元素分別運(yùn)用所遇到運(yùn)算符進(jìn)行運(yùn)算，并將

13、運(yùn)算結(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 為加號時(shí) */push(ps, num1 + num2); /*num1 與 num2 的和入棧 */if(c = '-') /*c 為減號時(shí) */push(ps, num1 - num2); /*

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

15、 suffixMAXNUM;int result;int flag = 1;while(flag = 1) printf(" 請輸入任意一個(gè)整數(shù)算術(shù)表達(dá)式 :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");四、上機(jī)調(diào)試1.編程中遇到的幾個(gè)問題剛看到題目的時(shí)候，我對題意沒有理解，運(yùn)用的普通的方法來完成程序，運(yùn)行時(shí)輸入無括 號的算術(shù)表達(dá)式可以正確輸出結(jié)果，但輸入帶括號的表達(dá)式時(shí)輸出的結(jié)果與運(yùn)算結(jié)果不符。 因此根據(jù)提示，設(shè)計(jì)算法將輸入的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式再運(yùn)算得到結(jié)果。在此算法 即最終使用的程序中，中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式函數(shù)中2、算法設(shè)計(jì)、調(diào)試的經(jīng)驗(yàn)和體會(huì)剛開始拿到這個(gè)

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

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

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

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

21、tack);/ 強(qiáng)制轉(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");/棧滿時(shí)輸出“滿溢! ”elsestack->

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

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

24、*/if(set= 1) suffixj+=' '/* 讀到數(shù)字時(shí)輸出一個(gè)空格 */ 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)棧不為空時(shí)*/c2=top(ps); /* 遇到右括號取棧頂*/pop(ps); /* 出棧 */if(c2 ='(')break; /*遇到左括號時(shí)停止出棧*/suffixj+=c2; /*c2 的值放入后綴表達(dá)式中 */if(c2 !=

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

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

28、 放入后綴表達(dá)式中 */else if(c2='+'|c2='-'|c2='(')break; /* 遇到乘除號時(shí)棧中棧頂元素是加減號和左括號時(shí)不進(jìn)行出棧*/*/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 值為左括號時(shí)*/f

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

30、m = 0, num1, num2; /* 定義 num1 、 num2 用于操作數(shù)間的運(yùn)算，并定義數(shù)據(jù)sum*/int i;char c;for(i = 0; suffixi != '0' i+) /* 中綴表達(dá)式不為空時(shí),遍歷表達(dá)式*/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 的計(jì)算 */else /*所遇到的不是操作數(shù) */sum = c - '0'/*sum 的計(jì)算 */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); /*遇到運(yùn)算符時(shí)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 為加號時(shí) */push(ps, num1 + num2); /*num1 與 num2 的和入棧 */ if(c = '-') /*c 為減號時(shí) */push(ps, num1 - num2); /*num1 與 num2 的差入棧 */ if(c = '*') /*c 為乘號時(shí) */push(ps, num1 * num2); /*num1 與 num2 的積入棧 */if(c = '/') /*c 為除號時(shí) */push(ps, nu