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

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

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

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

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

6、后綴表達(dá)式的計(jì)算，最后將結(jié)果顯示。下面給出的是用第一種算法實(shí)現(xiàn)的的程序的源代碼：#include #include #include /創(chuàng)建存放字符的結(jié)構(gòu)體 typedef structchar ch;/定義ch 存放操作符 int level;/定義level 存放操作符的優(yōu)先級(jí) OpNode;/創(chuàng)建字符棧 typedef structOpNode opNode100;int top;/存放棧頂?shù)臄?shù) int size;/存放當(dāng)前棧的大小 OpStack;/對(duì)字符棧的初始化 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)建一個(gè)返回值為double函數(shù)，用于兩個(gè)數(shù)的計(jì)算，傳入三個(gè)變量，/第一個(gè)變量為 操作數(shù)1，第二個(gè)變量為操作數(shù)2，第三個(gè)變量為操作符 double Cal(double num_1,double num_2,char op)double num = 0;/ 定義一個(gè)變量用于接收計(jì)算的結(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ù)為零，則推出程序并打印錯(cuò)誤信息 printf(ndivisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/創(chuàng)建一個(gè)返回值為int型的函數(shù)，用于比較兩個(gè)操作符的優(yōu)先級(jí) int Compare_opeate(int level_1,int level_2)if(level_1 = level_2

11、)/判斷優(yōu)先級(jí)別，返回相應(yīng)的值 return 0;return -1;/創(chuàng)建一個(gè)返回值為double型的函數(shù)，用于返回整個(gè)表達(dá)式的計(jì)算結(jié)果 double CalResult()/char ch = 23+12-34;/char ch = 19-(2*3)+12/2;char ch = (23-3)/0+12*2;char tempCh100; /存放后綴表達(dá)式 int index = 0,i = 0;OpStack ops;/定義 操作符棧 TdStack tds;/定義 操作數(shù)棧 OpNode op;/定義 字符節(jié)點(diǎn) TdNode td;/定義 數(shù)節(jié)點(diǎn) 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 = |) / 如是 | 則直接跳過(guò) k+;else / 如果是字符，則出棧兩

13、個(gè)數(shù) 進(jìn)行計(jì)算 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ù)，得到計(jì)算的結(jié)果 printf(nResult is ：);printf(%.2f,result);第二種算法對(duì)中綴表達(dá)式直接進(jìn)行計(jì)算，并將結(jié)果輸出，實(shí)現(xiàn)的源代碼：#include

14、#include #include /創(chuàng)建存放字符的結(jié)構(gòu)體 typedef structchar ch; /定義ch 存放操作符 int level;/定義level 存放操作符的優(yōu)先級(jí) OpNode;/創(chuàng)建字符棧 typedef structOpNode opNode100;int top;/存放棧頂?shù)臄?shù) int size;/存放當(dāng)前棧的大小 OpStack;/對(duì)字符棧的初始化 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)建一個(gè)返回值為double函數(shù)，用于兩個(gè)數(shù)的計(jì)算，傳入三個(gè)變量，/第一個(gè)變量為 操作數(shù)1，第二個(gè)變量為操作數(shù)2，第三個(gè)變量為操作符 double Cal(double num_1,double num_2,char op)double num = 0; / 定義一個(gè)變量用于接收計(jì)算的結(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ù)為零，則推出程序并打印錯(cuò)誤信息 printf(divisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/創(chuàng)建一個(gè)返回值為int型的函數(shù)，用于比較兩個(gè)操作符的優(yōu)先級(jí) int Compare_opeate(int level_1,int level_2)if(level_1 = level_2)/判斷優(yōu)先級(jí)別，返回相應(yīng)的值 return 0;return -1;/創(chuàng)建一個(gè)返回值為do

19、uble型的函數(shù)，用于返回整個(gè)表達(dá)式的計(jì)算結(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é)點(diǎn) TdNode td;/定義 數(shù)節(jié)點(diǎn) Op_init(&ops);/初始化字符棧 Td_init(&tds);/初始化操作數(shù)棧 while(chindex != 0)char chr = chindex; /

20、取出字符串的而一個(gè)字符 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;/判斷是否為加法或者減法運(yùn)算 if(chr = + | chr = -)op.ch = chr;/存放操作符到操作符節(jié)點(diǎn) op.level = 2; /給操作符賦值優(yōu)先級(jí) int level_2 = 2; /存放優(yōu)先級(jí)別，用于

21、比較優(yōu)先級(jí) while(ops.size != 0) /若字符棧不為空，則進(jìn)行字符的優(yōu)先級(jí)比較 int level_1 = Op_getTop(&ops).level;/兩個(gè)字符比較優(yōu)先級(jí)，若新的字符優(yōu)先級(jí)比棧中的字符優(yōu)先級(jí)高，則/從字符棧中字符出棧，同時(shí)從數(shù)棧中出棧兩個(gè)數(shù)，進(jìn)行計(jì)算，計(jì)算結(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) /若字符棧是空棧，則直接進(jìn)行入棧的操作 Op_push(&ops,op);index+;continue;/判斷是否為乘法或者除法的運(yùn)算符 if(chr = * | chr = /)op.ch = chr; /存放操作符到操作符節(jié)點(diǎn) op.level = 3; /給操作符賦值優(yōu)先級(jí) int level_2 = 3;/存放優(yōu)先級(jí)別，用于比較優(yōu)先級(jí)while(ops.size != 0)int level_1

23、= Op_getTop(&ops).level;/兩個(gè)字符比較優(yōu)先級(jí)，若新的字符優(yōu)先級(jí)比棧中的字符優(yōu)先級(jí)高，則/從字符棧中字符出棧，同時(shí)從數(shù)棧中出棧兩個(gè)數(shù)，進(jìn)行計(jì)算，計(jì)算結(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) /若字符棧是空棧，則直接進(jìn)行入棧的操作Op_push(&ops,op);index+;continue;/判斷是否為左括號(hào)，直接進(jìn)行入棧操作 if(chr = ()op.ch = chr;op.level = -1;Op_push(&ops,op);index+;continue;/判斷是否為右括號(hào) if(chr = )char ch1 = Op_getTop(&ops).ch;/進(jìn)行出棧的操作，知道遇到左括號(hào)為止。 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ù)，得到計(jì)算的結(jié)果 printf(Result is :);printf(%.2f,result);四、運(yùn)行結(jié)果中綴表達(dá)式直接進(jìn)行計(jì)算的運(yùn)行結(jié)果如下：圖 4 中綴表達(dá)式直接計(jì)算后綴轉(zhuǎn)中綴再進(jìn)行計(jì)算的運(yùn)行結(jié)果如下：圖 5 后綴表達(dá)式計(jì)算結(jié)果五、遇到的問(wèn)題及解決l 問(wèn)題1：從字符數(shù)組中截取出數(shù)字的操作，并轉(zhuǎn)化成浮點(diǎn)型的數(shù)不正確。計(jì)算的結(jié)果有時(shí)候是一

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

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