中綴表達式轉(zhuǎn)化成后綴表達式的計算_第1頁
中綴表達式轉(zhuǎn)化成后綴表達式的計算_第2頁
中綴表達式轉(zhuǎn)化成后綴表達式的計算_第3頁
中綴表達式轉(zhuǎn)化成后綴表達式的計算_第4頁
中綴表達式轉(zhuǎn)化成后綴表達式的計算_第5頁
已閱讀5頁,還剩14頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、目 錄一、設(shè)計思想.01二、算法流程圖.02三、源代碼.03四、運行結(jié)果.16五、遇到的問題及解決.17六、心得體會.18一、設(shè)計思想第一種算法先把算術(shù)表達式轉(zhuǎn)化成后綴表達式,在對后綴表達式進行計算。首先建立一個符號棧,用于存放字符和字符的優(yōu)先級別;然后在建立一個數(shù)棧,用于輔助后綴表達式的計算;最后在定義一個字符串數(shù)組,用于存放后綴表達式。建立一個計算的函數(shù),該函數(shù)用于兩個數(shù)的計算,在調(diào)用這個函數(shù)的時候,傳入三個參數(shù),兩個浮點型參數(shù)和一個字符型參數(shù),根據(jù)不同的符號進行不同的計算。定義一個判斷優(yōu)先級別的函數(shù),用于判斷兩個操作符的優(yōu)先級別,在根據(jù)優(yōu)先級的不同決定不同的操作。后綴表達式的取得,對算術(shù)

2、表達式字符串進行挨個的掃描,如果是數(shù)字或者是小數(shù)點,則將數(shù)字或者小數(shù)點存放到字符數(shù)組中,每取完一個數(shù)字,則在后面用“|”隔開,如果是操作符,則和棧中得操作符進行比較,若掃描到的符號優(yōu)先級比棧里的符號優(yōu)先級低,則棧中元素出棧并存放到字符數(shù)組中。每出一個字符到字符數(shù)組中就在后面加“|”分隔。繼續(xù)檢查棧頂比較優(yōu)先級,直到棧中元素優(yōu)先級比掃描到的符號優(yōu)先級低或者符號棧為空,則將此操作符入棧。若是“(”則無條件入字符棧,若是“)”則從字符棧中出字符直到遇到“(”為止。當字符數(shù)組掃描到最后的時候,計算并沒有結(jié)束。然后得進行字符棧的判斷,看是否已經(jīng)為空棧,若不是空棧,則出棧字符,將字符存放到數(shù)組中。最后字符

3、串數(shù)組中存放的就是后綴表達式。得到后綴表達式后,要用數(shù)棧進行后綴表達式的計算,后綴表達式的計算中,對新的數(shù)組進行從道到尾的掃描,如果遇到數(shù)字,以“|”為標記取出完整的操作數(shù),用輔助數(shù)組存放,然后轉(zhuǎn)化成浮點數(shù)存放到數(shù)棧中,遇到“|”則直接將數(shù)組下標往后走。遇到字符,則從數(shù)棧取出兩個數(shù)進行計算,將計算的結(jié)果從新存放到數(shù)棧中,循環(huán)直到接到結(jié)束。最后存放在數(shù)棧中的數(shù)就是計算的結(jié)果。最后在主函數(shù)中調(diào)用此函數(shù),進行結(jié)果的輸出。第二種算法對表達式直接進行計算,也稱為邊走邊計算首先建立一個符號棧,用于存放字符和字符的優(yōu)先級別;然后建立一個數(shù)棧,用于存放數(shù)。建立一個計算的函數(shù),該函數(shù)用于兩個數(shù)的計算,在調(diào)用這個

4、函數(shù)的時候,傳入三個參數(shù),兩個浮點型參數(shù)和一個字符型參數(shù),根據(jù)不同的符號進行不同的計算。定義一個判斷優(yōu)先級別的函數(shù),用于判斷兩個操作符的優(yōu)先級別,在根據(jù)優(yōu)先級的不同決定不同的操作。邊走邊計算實現(xiàn),掃描算術(shù)表達式,如果遇到數(shù)字或者是小數(shù)點,則進行循環(huán)的掃描直到將整個數(shù)字從字符數(shù)組中取出,把取出的字符存放到一個數(shù)組中,在利用c語言的函數(shù)把這個字符串的數(shù)字轉(zhuǎn)化成浮點型的數(shù)字,然后存放到數(shù)棧中,若果是字符,則將字符的優(yōu)先級與字符棧中的字符優(yōu)先級進行比較,若優(yōu)先級別低于字符棧中的符號優(yōu)先級別,則從字符棧中取出操作符,再從數(shù)棧中取出兩個數(shù)字,進行計算,計算的結(jié)果存放到數(shù)棧中,繼續(xù)檢查符號棧中的元素直到遇到

5、優(yōu)先級別比掃描到的字符優(yōu)先級別低或者符號棧為空,將掃描到的符號入棧。若是“(”則無條件入字符棧,若是“)”則從字符棧中出棧字符從數(shù)棧中取數(shù)進行計算,直到遇到“(”為止。當字符數(shù)組掃描到最后的時候,計算并沒有結(jié)束。然后得進行字符棧的判斷,看是否已經(jīng)為空棧,若不是空棧,則出棧字符,每出棧一個字符就出棧兩個數(shù)字,進行計算,直到字符棧空為止。最終存放在數(shù)棧中的數(shù)就是計算的結(jié)果。最后在主函數(shù)中調(diào)用此函數(shù),進行結(jié)果的輸出。二、算法流程圖第一種算法:先將中綴表達式轉(zhuǎn)化成后綴表達式,然后計算。圖1中綴轉(zhuǎn)后綴流程圖圖 2 后綴表達式的計算圖 3 直接計算中綴表達式三、源代碼先將中綴表達式轉(zhuǎn)化成后綴表達式,在進行

6、后綴表達式的計算,最后將結(jié)果顯示。下面給出的是用第一種算法實現(xiàn)的的程序的源代碼:#include #include #include /創(chuàng)建存放字符的結(jié)構(gòu)體 typedef structchar ch;/定義ch 存放操作符 int level;/定義level 存放操作符的優(yōu)先級 OpNode;/創(chuàng)建字符棧 typedef structOpNode opNode100;int top;/存放棧頂?shù)臄?shù) int size;/存放當前棧的大小 OpStack;/對字符棧的初始化 void Op_init(OpStack *ops)ops-top = 0;ops-size = 0;/字符棧的入棧操作

7、 void Op_push(OpStack *ops,OpNode op)ops-size+;ops-opNode(ops-top)+ = op;/字符棧的出棧操作 OpNode Op_pop(OpStack *ops)if(ops-size = 0)/判斷棧是否為空,如果為空,則退出程序,否則出棧exit(-1);ops-size-;return ops-opNode-(ops-top);/看字符棧頂操作 OpNode Op_getTop(OpStack *ops)int len = ops-size;return ops-opNodelen - 1;/創(chuàng)建存放數(shù)的結(jié)構(gòu)體 typedef s

8、tructdouble d;/定義 d 存放操作數(shù) TdNode;/創(chuàng)建數(shù)棧 typedef structTdNode tdNode100;int size;int top;TdStack;/數(shù)棧的初始化 void Td_init(TdStack *tds)tds-size = 0; tds-top = 0;/數(shù)棧的入棧 void Td_push(TdStack *tds,TdNode td)tds-size+;tds-tdNode(tds-top)+ = td;/數(shù)棧的出棧 TdNode Td_pop(TdStack *tds)if(tds-size = 0)/判斷棧是否為空,如果為空,則退

9、出程序,否則出棧exit(-1);tds-size-;return tds-tdNode-(tds-top);/看數(shù)棧棧頂 TdNode Td_getTop(TdStack *tds)int len = tds-size;return tds-tdNodelen - 1;/創(chuàng)建一個返回值為double函數(shù),用于兩個數(shù)的計算,傳入三個變量,/第一個變量為 操作數(shù)1,第二個變量為操作數(shù)2,第三個變量為操作符 double Cal(double num_1,double num_2,char op)double num = 0;/ 定義一個變量用于接收計算的結(jié)果 switch(op)case +:n

10、um = num_1 + num_2;break;case -:num = num_1 - num_2;break;case *:num = num_1 * num_2;break;case /:if(num_2 = 0) / 如果除數(shù)為零,則推出程序并打印錯誤信息 printf(ndivisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/創(chuàng)建一個返回值為int型的函數(shù),用于比較兩個操作符的優(yōu)先級 int Compare_opeate(int level_1,int level_2)if(level_1 = level_2

11、)/判斷優(yōu)先級別,返回相應的值 return 0;return -1;/創(chuàng)建一個返回值為double型的函數(shù),用于返回整個表達式的計算結(jié)果 double CalResult()/char ch = 23+12-34;/char ch = 19-(2*3)+12/2;char ch = (23-3)/0+12*2;char tempCh100; /存放后綴表達式 int index = 0,i = 0;OpStack ops;/定義 操作符棧 TdStack tds;/定義 操作數(shù)棧 OpNode op;/定義 字符節(jié)點 TdNode td;/定義 數(shù)節(jié)點 Op_init(&ops);/初始化字

12、符棧 Td_init(&tds);/初始化操作數(shù)棧 while(chindex != 0)char chr = chindex;if(chr = 0 & chr = 0 & chr = 0 & cc = 0 & cc = 9 | cc = .)asschi+ = tempChtempIndex;tempIndex+;cc = tempChtempIndex;td.d = atof(assch);Td_push(&tds,td); /將取出的操作數(shù)入棧 k = tempIndex;continue;else if(cc = |) / 如是 | 則直接跳過 k+;else / 如果是字符,則出棧兩

13、個數(shù) 進行計算 char op1 = cc;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);k+;return Td_pop(&tds).d;main()double result = CalResult(); /調(diào)用函數(shù),得到計算的結(jié)果 printf(nResult is :);printf(%.2f,result);第二種算法對中綴表達式直接進行計算,并將結(jié)果輸出,實現(xiàn)的源代碼:#include

14、#include #include /創(chuàng)建存放字符的結(jié)構(gòu)體 typedef structchar ch; /定義ch 存放操作符 int level;/定義level 存放操作符的優(yōu)先級 OpNode;/創(chuàng)建字符棧 typedef structOpNode opNode100;int top;/存放棧頂?shù)臄?shù) int size;/存放當前棧的大小 OpStack;/對字符棧的初始化 void Op_init(OpStack *ops)ops-top = 0;ops-size = 0;/字符棧的入棧操作 void Op_push(OpStack *ops,OpNode op)ops-size+;o

15、ps-opNode(ops-top)+ = op;/字符棧的出棧操作 OpNode Op_pop(OpStack *ops)if(ops-size = 0)/判斷棧是否為空,如果為空,則退出程序,否則出棧 exit(-1);ops-size-;return ops-opNode-(ops-top);/看字符棧頂操作 OpNode Op_getTop(OpStack *ops)int len = ops-size;return ops-opNodelen - 1;/創(chuàng)建存放數(shù)的結(jié)構(gòu)體 typedef structdouble d;/定義 d 存放操作數(shù) TdNode;/創(chuàng)建數(shù)棧 typedef

16、structTdNode tdNode100;int size;int top;TdStack;/數(shù)棧的初始化 void Td_init(TdStack *tds)tds-size = 0; tds-top = 0;/數(shù)棧的入棧 void Td_push(TdStack *tds,TdNode td)tds-size+;tds-tdNode(tds-top)+ = td;/數(shù)棧的出棧 TdNode Td_pop(TdStack *tds)if(tds-size = 0)/判斷棧是否為空,如果為空,則退出程序,否則出棧 exit(-1);tds-size-;return tds-tdNode-(

17、tds-top);/看數(shù)棧棧頂 TdNode Td_getTop(TdStack *tds)int len = tds-size;return tds-tdNodelen - 1;/創(chuàng)建一個返回值為double函數(shù),用于兩個數(shù)的計算,傳入三個變量,/第一個變量為 操作數(shù)1,第二個變量為操作數(shù)2,第三個變量為操作符 double Cal(double num_1,double num_2,char op)double num = 0; / 定義一個變量用于接收計算的結(jié)果 switch(op)case +:num = num_1 + num_2;break;case -:num = num_1 -

18、 num_2;break;case *:num = num_1 * num_2;break;case /:if(num_2 = 0) / 如果除數(shù)為零,則推出程序并打印錯誤信息 printf(divisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/創(chuàng)建一個返回值為int型的函數(shù),用于比較兩個操作符的優(yōu)先級 int Compare_opeate(int level_1,int level_2)if(level_1 = level_2)/判斷優(yōu)先級別,返回相應的值 return 0;return -1;/創(chuàng)建一個返回值為do

19、uble型的函數(shù),用于返回整個表達式的計算結(jié)果 double CalResult()/char ch = 23+12-34;char ch = 19-(2*3)+12/0;/char ch = (23-3)/2+12*2;int index = 0; /定義字符串的索引 OpStack ops;/定義 操作符棧 TdStack tds;/定義 操作數(shù)棧 OpNode op;/定義 字符節(jié)點 TdNode td;/定義 數(shù)節(jié)點 Op_init(&ops);/初始化字符棧 Td_init(&tds);/初始化操作數(shù)棧 while(chindex != 0)char chr = chindex; /

20、取出字符串的而一個字符 if(chr = 0 & chr = 0 & chr = 9 | chr = .) tempChi+ = chtempIndex;tempIndex+;chr = chtempIndex;td.d = atof(tempCh); Td_push(&tds,td);/把取出的操作數(shù)存放到操作數(shù)棧 index = tempIndex;continue;/判斷是否為加法或者減法運算 if(chr = + | chr = -)op.ch = chr;/存放操作符到操作符節(jié)點 op.level = 2; /給操作符賦值優(yōu)先級 int level_2 = 2; /存放優(yōu)先級別,用于

21、比較優(yōu)先級 while(ops.size != 0) /若字符棧不為空,則進行字符的優(yōu)先級比較 int level_1 = Op_getTop(&ops).level;/兩個字符比較優(yōu)先級,若新的字符優(yōu)先級比棧中的字符優(yōu)先級高,則/從字符棧中字符出棧,同時從數(shù)棧中出棧兩個數(shù),進行計算,計算結(jié)/果存入數(shù)棧,否則將新的字符入棧 if(Compare_opeate(level_1,level_2) = 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num

22、= Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);elseOp_push(&ops,op);break;if(ops.size = 0) /若字符棧是空棧,則直接進行入棧的操作 Op_push(&ops,op);index+;continue;/判斷是否為乘法或者除法的運算符 if(chr = * | chr = /)op.ch = chr; /存放操作符到操作符節(jié)點 op.level = 3; /給操作符賦值優(yōu)先級 int level_2 = 3;/存放優(yōu)先級別,用于比較優(yōu)先級while(ops.size != 0)int level_1

23、= Op_getTop(&ops).level;/兩個字符比較優(yōu)先級,若新的字符優(yōu)先級比棧中的字符優(yōu)先級高,則/從字符棧中字符出棧,同時從數(shù)棧中出棧兩個數(shù),進行計算,計算結(jié)/果存入數(shù)棧,否則將新的字符入棧 if(Compare_opeate(level_1,level_2) = 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);elseOp_pu

24、sh(&ops,op);break;if(ops.size = 0) /若字符棧是空棧,則直接進行入棧的操作Op_push(&ops,op);index+;continue;/判斷是否為左括號,直接進行入棧操作 if(chr = ()op.ch = chr;op.level = -1;Op_push(&ops,op);index+;continue;/判斷是否為右括號 if(chr = )char ch1 = Op_getTop(&ops).ch;/進行出棧的操作,知道遇到左括號為止。 while(ch1 != ()char op1 = Op_pop(&ops).ch;double num_2

25、 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);ch1 = Op_getTop(&ops).ch;Op_pop(&ops);index+;continue;/如果字符棧不為空,則一直出棧直到字符棧為空。 while(ops.size != 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;doubl

26、e num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);/將結(jié)果出棧返回 return Td_pop(&tds).d;main()double result = CalResult(); /調(diào)用函數(shù),得到計算的結(jié)果 printf(Result is :);printf(%.2f,result);四、運行結(jié)果中綴表達式直接進行計算的運行結(jié)果如下:圖 4 中綴表達式直接計算后綴轉(zhuǎn)中綴再進行計算的運行結(jié)果如下:圖 5 后綴表達式計算結(jié)果五、遇到的問題及解決l 問題1:從字符數(shù)組中截取出數(shù)字的操作,并轉(zhuǎn)化成浮點型的數(shù)不正確。計算的結(jié)果有時候是一

27、個意想不到的很大的數(shù)。問題1的解決方法:從字符數(shù)數(shù)組中將數(shù)字截取出來就是為了能進行計算,而數(shù)字是單個字符的形式存在,必須把一個完整的數(shù)從算術(shù)表達式中截取出來,如果遇到數(shù)字的字符就是一個數(shù)字的入口,然后循環(huán)取出直到遇到不是數(shù)字或者小數(shù)點為止。而這些取出的數(shù)字是一堆離散的數(shù)字字符。這時候就需要建立一個輔助的數(shù)組來存放這些數(shù)字字符以組成一個數(shù)字的字符。用一個輔助的索引將數(shù)字的組成字符一個一個從數(shù)組中取出來,存放到新的數(shù)組中,以得到一個字符串的數(shù)字。從數(shù)組中截取出一個數(shù)后,將取出的數(shù)用atof 函數(shù)進行轉(zhuǎn)化成浮點型的數(shù)。在把浮點型的數(shù)存放到數(shù)棧中,在后面的計算中取出。在調(diào)試中第一個取出的浮點型數(shù)是正確

28、的,當遇到后面截取的數(shù)的長度比第一個數(shù)短的時候,發(fā)現(xiàn)取出的數(shù)和第一個數(shù)的位數(shù)相同了。經(jīng)過分析,每次截取完數(shù)字后并沒有對輔助數(shù)組進行重新的初始化,數(shù)組中宗存放著前一個字符,一旦遇到數(shù)字比前面的數(shù)字短的的情況,后面的數(shù)字只覆蓋了前面的數(shù)字的前幾位,后面的幾位都是原先的數(shù)字。造成取出的結(jié)果是錯誤的。解決問題的方法可以在每次存放數(shù)字之前,把輔助數(shù)組進行初始化,結(jié)果能正確計算表達式。l 問題2:如何生成后綴表達式,將數(shù)與字符存放在一個字符串中。問題2的解決方法:想把數(shù)字從字符數(shù)組中取出來,然后再存入后綴表達式中,從字符數(shù)組中取出是很容易的,但是在把這些數(shù)字和操作符進行存入一個后綴表達式數(shù)的時候出現(xiàn)了問題,因為c 語言中沒有這樣的字符數(shù)組,所以取出的數(shù)字根本沒法和操作符一塊存到一個數(shù)組中去。改變一種想問題的方法,就是不把字符數(shù)組的數(shù)字都截取出來,而是把數(shù)字進行一個分割,讓數(shù)字還依舊存放在數(shù)組中,只是在每個數(shù)字的后面都加上一個分割符

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論