中綴表達式轉(zhuǎn)化成后綴表達式的計算

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ù)字的后面都加上一個分割符