c++課程設(shè)計(jì)報(bào)告(二叉樹運(yùn)算)

1、南京理工大學(xué) 課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：二叉樹解決四則運(yùn)算問題 院系:自動(dòng)化院 班級(jí)：2002 學(xué)號(hào)：912110200330 姓名：袁佳泉 指導(dǎo)老師：閆玉德 時(shí)間：2013年3月24一程序功能簡(jiǎn)介利用二叉樹的結(jié)構(gòu)解決帶括號(hào)的四則運(yùn)算的問題。程序利用二叉樹的堆棧將二叉樹的結(jié)點(diǎn)變成結(jié)點(diǎn)中的數(shù)據(jù)時(shí)運(yùn)算符，左右子樹是標(biāo)準(zhǔn)結(jié)點(diǎn)形式，或是另外的標(biāo)準(zhǔn)二叉樹形式，通過后序遍歷，經(jīng)標(biāo)準(zhǔn)結(jié)點(diǎn)中的表達(dá)式求出。二 課程設(shè)計(jì)要求(1) 讀懂程序，將程序的運(yùn)算步驟完整的描述出來。(2) 四則運(yùn)算的表達(dá)式可以接受空格輸入(3) 依照運(yùn)算順序依次輸出四則運(yùn)算每一步的算式及及結(jié)果，最后輸出最終計(jì)算結(jié)果三 課程設(shè)計(jì)思想這個(gè)課題設(shè)

2、計(jì)要求最關(guān)鍵的就是讀懂程序，用類實(shí)現(xiàn)四則運(yùn)算其實(shí)不是很難，只是利用二叉樹實(shí)現(xiàn)帶括號(hào)的四則運(yùn)算有些難度。初讀源程序覺得摸不到頭腦，幾遍下來還是能夠理解的。在程序中先計(jì)算的式子放在棧頂，首先賦值右子樹，再賦值左子樹，保證優(yōu)先級(jí)。如圖： 二叉樹類棧 運(yùn)算符棧 ）*（+ 輸入“+”，“（”，“*”三個(gè)運(yùn)算符沒有優(yōu)先級(jí)沖突，按順序壓棧，然后輸入“”，優(yōu)先級(jí)低于“*”，binary_tree temp_tree; /生成二叉樹string thisstring=""thisstring = thisstring + OpStack.top();OpStack.pop() /將棧頂優(yōu)先級(jí)

3、高的運(yùn)算符移除（即這邊的乘號(hào)）etree.root = build_node(thisstring);/將優(yōu)先級(jí)高的運(yùn)算符作為二叉樹的根結(jié)點(diǎn)copy(temp_tree.root,NodeStack.top().root);/將二叉樹堆棧棧頂?shù)亩鏄鋸?fù)制到新生成的二叉樹中（即把1復(fù)制到新的二叉樹中）NodeStack.pop();/移除二叉樹棧棧頂etree.root->right_child = temp_tree.root;/將二叉樹作為新二叉樹的右分支temp_tree.root = NULL;copy(temp_tree.root,NodeStack.top().root); /

4、繼續(xù)將下一個(gè)棧頂二叉樹復(fù)制（即把5復(fù)制）etree.root->left_child = temp_tree.root;/成為新二叉樹的左分支NodeStack.pop();/移除temp_tree.root = NULL;copy(temp_tree.root, etree.root);NodeStack.push(temp_tree);/新二叉樹進(jìn)棧etree.root = NULL;OpStack.push(c);/優(yōu)先級(jí)低的運(yùn)算符壓棧過程如圖： 棧頂二叉樹 temp_tree二叉樹 Etree二叉樹 將temp_tree作為etree的右結(jié)點(diǎn) 新的二叉樹類棧最后進(jìn)行一個(gè)遍歷，判斷

5、運(yùn)算符棧是否處理完，算出最后結(jié)果。四 增加的模塊（1）對(duì)源程序進(jìn)行兩處修改使其能夠按運(yùn)算順序依次輸出四則運(yùn)算每一步的算式及結(jié)果。程序如下：Static int count=0;count+;if(count=1)cout<<"運(yùn)算過程及結(jié)果是"cout<<num1<<prt->data<<num2<<"="<<num<<'t'五 優(yōu)化程序源程序未能實(shí)現(xiàn)負(fù)數(shù)運(yùn)算，只能在正數(shù)范圍內(nèi)運(yùn)算。于是便試圖把范圍推廣到整個(gè)實(shí)數(shù)。改編程序如下：if(isok(inf

6、ix) static int m=0,n=0 ;for(int i=0; i < infix.size(); i+) c = infixi;if(IsOperand(c) if(NodeStack.top().root->right_child=0&&NodeStack.top().root->left_child=0&&NodeStack.top().root!=0) string tempstring;tempstring = tempstring + c;if(i+1 < infix.size() && IsOper

7、and(infixi+1)/輸入多位數(shù) while(i+1 < infix.size() && IsOperand(infixi+1) tempstring = tempstring + infix+i;binary_tree temp;temp.root = build_node(tempstring);copy(temp.root,NodeStack.top().root); NodeStack.pop(); etree.root->left_child=temp.root;temp.root=NULL;NodeStack.push(etree);elsestr

8、ing tempstring;tempstring = tempstring + c;if(i+1 < infix.size() && IsOperand(infixi+1)/輸入多位數(shù) while(i+1 < infix.size() && IsOperand(infixi+1) tempstring = tempstring + infix+i;binary_tree temp;temp.root = build_node(tempstring);NodeStack.push(temp); n+;else if(c = '+' |

9、 c = '-' | c = '*' | c = '/' | c = '') if(OpStack.empty()OpStack.push(c);m+;else if(OpStack.top() = '(')OpStack.push(c);m+;else if(TakesPrecedence(c, OpStack.top()OpStack.push(c);m+;else if(c='-'&&m=n)binary_tree temp_tree;string thisstring=""thisstring=thisstring+'-'etree.root=build_node(thisstring);string thiss=""thiss=thiss+'0'temp_tree.root=build_node(thiss); etree.root->right_child=temp_tree.root; temp_tree.root=NULL; NodeStack.push(temp_tree);/新二叉樹進(jìn)棧 etree.root = N