2022年中缀表达式改为后缀表达式实验报告附C源码二叉树

1、中缀表达式改后缀表达式一、需求分析1.本程序采用的是二叉树后序遍历来实现四则运算的中缀表达式改为后缀表达式；2.需要用一个类来代表数据的结构；3. 输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。二、概要设计抽象数据类型用Node 类来定义一个结点：class Nodepublic:char chmax; /每个结点的字符串Node* lChild; /左指针Node* rChild; /右指针Node();Node();算法

2、的基本思想输入中缀表达式，用函数对字符串中的空格或者等号进行处理，由于程序需要，会在输入的字符串结尾加入=；用函数一次扫描每一个字符，有异常字符，报错；没有，则每次取出连续的数字字符或加减乘除的符号，放入结点，并按规则，将上一结点的左或右指针指向该结点；退出将该树用后序遍历法，输出每个结点的值；程序的流程输入四则中缀表达式逐一扫描，判断是否有错处理表达式逐一产生结点，相关结点的左或右指针指向该结点输出算法的具体步骤处理：将表达式中的空格和多余的等号删掉，在表达式的最后加上等号；扫描：扫描过程在树的建立过程中；每次扫描，获得数字字符作为一个结点，并返回数字字符后的算数运算符或者括号；根据返回的运

3、算符或括号，确定相应的指针赋值或是新建结点；（有错时，会退出程序）后序遍历法输出获得结果。算法的时空分析因为在处理字符串时，需要逐一扫描，也建立了新的字符数组，所以时间复杂度为(n);同样，扫描的循环，也与字符串的长度有关，时间复杂度也为(n)输入和输出的格式输入：3.4+5*(2*（4+5）+7)输出：3.4 5 2 4 5 + * 7 + * +五、测试结果六、实验总结这个程序好难，自己很难想到这方法。不过，没想法时，看不懂别人的程序时，可以通过调试的方法，去获取程序的主要思想，从而变为自己的想法，去实现他。代码嘛，主要是多写，多仿，写代码的能力自然而然就提高了。七、附录（可选）#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;/保存原始的中缀表达式static char str2*ma

5、x;/保存后序遍历出来的字符串，为表达式求值提供方便static int k=0;void enter ();/输入函数char getOp(Node *temp);/temp指针保存每个接点的,返回的是运算符或者Node* crtTree(Node* root); /传入根结点指针，返回根结点指针void output(Node *root);/获得处理后的字符串 bool isError(char);/判断字符是否有问题void deal(); /对字符数组进行处理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)/将数字字符存入一/个结点，并返回数字字符的后一个符号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);/递归创建/括号里的指针op=arraycount;count+;break;elsep-rChild=crtTree(p-rChild);/递归创 /建括号里的指针op=arraycount;count+;break;case ): return root;return root;void output(Node *root) /传入根结点，后/序遍历历赋值给另一个字符数组（主要是/为了给后序的计算表达式值提供方便）int n;if(root)output(root-lChild);output(root-rChild);n=0;while(root-chn!=0)strk+=root-chn+;strk+= ;bool isError(char ch) /判断每个字符/是否有错if(ch!=+&ch!=-&ch!=*&ch!=/&!(ch=0)&ch!=.&ch!=(&ch!=)co