2022年中綴表達(dá)式改為后綴表達(dá)式實(shí)驗(yàn)報(bào)告附C源碼二叉樹

1、中綴表達(dá)式改后綴表達(dá)式一、需求分析1.本程序采用的是二叉樹后序遍歷來實(shí)現(xiàn)四則運(yùn)算的中綴表達(dá)式改為后綴表達(dá)式；2.需要用一個(gè)類來代表數(shù)據(jù)的結(jié)構(gòu)；3. 輸入輸出格式：輸入：在字符界面上輸入一個(gè)中綴表達(dá)式，回車表示結(jié)束。輸出：如果該中綴表達(dá)式正確，那么在字符界面上輸出其后綴表達(dá)式，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達(dá)式錯(cuò)誤提示。二、概要設(shè)計(jì)抽象數(shù)據(jù)類型用Node 類來定義一個(gè)結(jié)點(diǎn)：class Nodepublic:char chmax; /每個(gè)結(jié)點(diǎn)的字符串Node* lChild; /左指針Node* rChild; /右指針Node();Node();算法

2、的基本思想輸入中綴表達(dá)式，用函數(shù)對(duì)字符串中的空格或者等號(hào)進(jìn)行處理，由于程序需要，會(huì)在輸入的字符串結(jié)尾加入=；用函數(shù)一次掃描每一個(gè)字符，有異常字符，報(bào)錯(cuò)；沒有，則每次取出連續(xù)的數(shù)字字符或加減乘除的符號(hào)，放入結(jié)點(diǎn)，并按規(guī)則，將上一結(jié)點(diǎn)的左或右指針指向該結(jié)點(diǎn)；退出將該樹用后序遍歷法，輸出每個(gè)結(jié)點(diǎn)的值；程序的流程輸入四則中綴表達(dá)式逐一掃描，判斷是否有錯(cuò)處理表達(dá)式逐一產(chǎn)生結(jié)點(diǎn)，相關(guān)結(jié)點(diǎn)的左或右指針指向該結(jié)點(diǎn)輸出算法的具體步驟處理：將表達(dá)式中的空格和多余的等號(hào)刪掉，在表達(dá)式的最后加上等號(hào)；掃描：掃描過程在樹的建立過程中；每次掃描，獲得數(shù)字字符作為一個(gè)結(jié)點(diǎn)，并返回?cái)?shù)字字符后的算數(shù)運(yùn)算符或者括號(hào)；根據(jù)返回的運(yùn)

3、算符或括號(hào)，確定相應(yīng)的指針賦值或是新建結(jié)點(diǎn)；（有錯(cuò)時(shí)，會(huì)退出程序）后序遍歷法輸出獲得結(jié)果。算法的時(shí)空分析因?yàn)樵谔幚碜址畷r(shí)，需要逐一掃描，也建立了新的字符數(shù)組，所以時(shí)間復(fù)雜度為(n);同樣，掃描的循環(huán)，也與字符串的長(zhǎng)度有關(guān)，時(shí)間復(fù)雜度也為(n)輸入和輸出的格式輸入：3.4+5*(2*（4+5）+7)輸出：3.4 5 2 4 5 + * 7 + * +五、測(cè)試結(jié)果六、實(shí)驗(yàn)總結(jié)這個(gè)程序好難，自己很難想到這方法。不過，沒想法時(shí)，看不懂別人的程序時(shí)，可以通過調(diào)試的方法，去獲取程序的主要思想，從而變?yōu)樽约旱南敕?，去?shí)現(xiàn)他。代碼嘛，主要是多寫，多仿，寫代碼的能力自然而然就提高了。七、附錄（可選）#incl

4、ude#includeusing namespace std;const int max=100;class Nodepublic:char chmax;Node* lChild;Node* rChild;Node();Node();Node:Node()strcpy(ch,);lChild=rChild=NULL;Node:Node()if(lChild!=NULL)delete lChild;if(rChild!=NULL)delete rChild;static int count=0;static char arraymax;/保存原始的中綴表達(dá)式static char str2*ma

5、x;/保存后序遍歷出來的字符串，為表達(dá)式求值提供方便static int k=0;void enter ();/輸入函數(shù)char getOp(Node *temp);/temp指針保存每個(gè)接點(diǎn)的,返回的是運(yùn)算符或者Node* crtTree(Node* root); /傳入根結(jié)點(diǎn)指針，返回根結(jié)點(diǎn)指針void output(Node *root);/獲得處理后的字符串 bool isError(char);/判斷字符是否有問題void deal(); /對(duì)字符數(shù)組進(jìn)行處理int main()Node* root=NULL;cin.getline(array,40);deal();root=crt

6、Tree(root);output(root);cout str;return 0;char getOp(Node *temp)/將數(shù)字字符存入一/個(gè)結(jié)點(diǎn)，并返回?cái)?shù)字字符的后一個(gè)符號(hào)int i=0;if(isError(arraycount)exit(0);while(arraycount=0|arraycount=.)temp-chi=arraycount;i+;count+;temp-chi=0;count+;return arraycount-1;Node* crtTree(Node* root)Node *p,*q;char op;if(root=NULL)root=new Node;

7、p=new Node;op=getOp(root);while(op!=)q=new Node;q-ch0=op;q-ch1=0;switch(op)case +:case -: q-lChild=root;root=q;p=new Node;op=getOp(p);root-rChild=p;break;case *:case /:if(root-ch0=+|root-ch0=-) p=new Node; strcpy(p-ch,root-ch); p-lChild=root; p-rChild=q; op=getOp(root); root=p; elseq-lChild=root;roo

8、t=q;p=new Node;op=getOp(p);root-rChild=p;break;case (:p=root;while(p-rChild)p=p-rChild;if(p-lChild=NULL)p-lChild=crtTree(p-lChild);/遞歸創(chuàng)建/括號(hào)里的指針op=arraycount;count+;break;elsep-rChild=crtTree(p-rChild);/遞歸創(chuàng) /建括號(hào)里的指針op=arraycount;count+;break;case ): return root;return root;void output(Node *root) /傳入根結(jié)點(diǎn)，后/序遍歷歷賦值給另一個(gè)字符數(shù)組（主要是/為了給后序的計(jì)算表達(dá)式值提供方便）int n;if(root)output(root-lChild);output(root-rChild);n=0;while(root-chn!=0)strk+=root-chn+;strk+= ;bool isError(char ch) /判斷每個(gè)字符/是否有錯(cuò)if(ch!=+&ch!=-&ch!=*&ch!=/&!(ch=0)&ch!=.&ch!=(&ch!=)co