《数据结构实验报告五—四则运算表达式求值》由会员分享，可在线阅读，更多相关《数据结构实验报告五—四则运算表达式求值（10页珍藏版）》请在金锄头文库上搜索。
1、问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。一、需求分析：1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的 结果来求解后缀表达式的值。2、输入输出格式：输入格式：在字符界面上输入一个中缀表达式，回车表示结束。请输入表达式：输入一个中缀表达式输出格式：如果该中缀表达式正确， 那么在字符界面上输出其后缀表达 式，其中后缀表达式中两相邻操作数之间利用空格隔开；如 果不正确，在字符界面上输出表达式错误提示。逆波兰表达式为：输出逆波兰表达式运算结果为：输出运算后的结果3、测试用例输入： 21+23*（12-6）输出： 21 23 1
2、2 6 -*+二、概要设计：抽象数据类型 二叉树类 BiTree 算法的基本思想 根据题目要求，利用栈计算，和二叉树存储，来计算表达式 该算法的基本思想是： 先利用栈进行计算， 然后用二叉树进行存储， 和实验三算法一样来计算逆波 兰表达式的值 程序的流程 程序由三个模块组成： （1）输入模块：输入一个运算式（2）计算模块：利用栈进行表达式的计算，二叉树来存储。 （3 ） 输出模块：屏幕上显示出后缀表达式和运算结果。三、详细设计物理数据类型 程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree 包含私有成员struct BiTreeNode，根节点BiTreeNode *T;
3、 索引 index; int number_of_point 优先级比较函数 compare(char a,char b);生成树的函数 void InorderCreate(BiTreeNode * 判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T); 还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函 数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。 算法的时空分析 此算法利用栈和二叉树来实现，故次算法的的时间复杂度为（N） 。 输入和输出的格式输入格式：
4、请输入表达式：输入一个中缀表达式 /回车输出格式：逆波兰表达式为：输出逆波兰表达式运算结果为：输出运算后的结果四、调试分析略。五、测试结果本实验的测试结果截图如下：六、用户使用说明（可选）1 、 本程序的运行环境为windows 操作系统，执行文件为 biaodashi.exe 2 、运行程序时 提示输入表达式本程序可以将中缀表达式转换为后缀表达式后在计算出运算式的结果。 提示：请输入表达式： 输出 提示：逆波兰表达式为： 运算结果：七、实验心得（可选）本次实验过程比较复杂， 由于书上的知识掌握的还不是很牢靠，所以现在实 验做起来有点儿吃力。本实验主要是通过与同学的讨论和课后查阅资料来完成 的
5、，虽然有些地方还不是很懂， 但基本上能完成此次实验的内容。而且通过本次 实验，加深了对二叉树算法的了解。附录（实验代码） ：#include #include #include #include #include #include #define STACK_INIT_SIZE 100 #define DATA_SIZE 10 #define STACKINCREMENT 10 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -2 using namespace std; typedef
6、float SElemtype; typedef int Status; typedef char * TElemType; typedef struct BiTNode TElemType data; int len; /data 字符串中字符的个数struct BiTNode * lchild, * rchild; BiTNode, *BiTree; typedef struct SElemtype *base; SElemtype *top; int stacksize; SqStack; Status IsDigital(char ch) if(ch=0 int i=0; T = (B
7、iTNode *)malloc(sizeof(BiTNode); T-data = (char *)malloc(DATA_SIZE*sizeof(char); while(IsDigital(ci) T-data i = ci; i+; T-len = i; T-lchild = T-rchild = NULL; PTR.push (T); return i; void CrtSubTree(stack T = (BiTNode *)malloc(sizeof(BiTNode); T-data = (char *)malloc(DATA_SIZE*sizeof(char); T-data 0
8、 = c; T-len = 1; T-rchild = PTR.top(); / 先右子树，否则运算次序反了PTR.pop (); T-lchild = PTR.top(); PTR.pop (); PTR.push (T); char symbol55=, , , /符号优先级, , , , , , , , , , , , , PTR;/ 存放表达式树中的节点指针stack OPTR;/ 存放操作符char op; int i=0; OPTR.push (#); op = OPTR.top(); while( !(expi=#) else if (expi = ) i+; else swit
9、ch (expi) case (: OPTR.push (expi); i+; break; case ): op = OPTR.top (); OPTR.pop (); while(op!=() CrtSubTree(PTR, op); op = OPTR.top (); OPTR.pop (); /end while i+; break; default: /expi 是 + - * / while(! OPTR.empty () op = OPTR.top (); if (Precede(op, expi)=) CrtSubTree(PTR, op); OPTR.pop (); if(e
10、xpi!=#) OPTR.push (expi); i+; break; /end switch /end else /end while T = PTR.top(); PTR.pop (); void PostOrderTraverse(BiTree PostOrderTraverse(T-rchild,exp,count); strncpy(exp+count,T-data,T-len); expcount+=(T-len)= ; count+; /逆波兰表达式计算填空Status InitStack(SqStack if (! S.base) exit(OVERFLOW); S.top
11、= S.base; S.stacksize = STACK_INIT_SIZE; /printf(“ 程序运行到构建栈n“); return OK; int StackLength(SqStack S) return S.top-S.base; /printf(“ 程序运行到获得堆栈元素的个数n“); /获得堆栈元素的个数 Status Push(SqStack if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /printf(“ 程序运行到入栈n“); r
12、eturn OK; /入栈 Status Pop(SqStack e=*-S.top; / printf(“ 程序运行到出栈n“); return OK; /出栈 int EvalValue(char *ch, SqStack SElemtype result=0; char a; a=chi; while(IsDigital(a) result=10*result+(int)(a-48); a=ch+i; Push(S, result); /printf(“ 程序运行标志1n“); return i; void EvalExpr(char ch, SqStack if(ch=+)|(ch=-
13、)|(ch=*)|(ch=/) Pop(S,p); Pop(S,q); switch(ch) case +:r=p+q; break; case -:r=q-p; break; case *:r=q*p; break; case /:r=q/p; break; default:; Push(S,r); /printf(“ 程序运行标志2n“); /如果 ch 中保存的是操作符， 则从堆栈中弹出两个元素，并把操作符应用在这两个元素之上，然后把操作结果压入到栈中。如果试图从栈中弹出两个元素是，该栈中并没有， 那么该后缀表达式是不正确的。 Status evaluate (char ch, floa
14、t Status St; int i; i=0; St = InitStack(S); while(chi!=# else if(chi= ) i+; else EvalExpr(chi, S); i+; /如果到达表达式末尾时，栈中剩余元素不止一个，那么该/后缀表达式是不正确的。if(StackLength(S) =1) Pop(S, result); else /printf(“ 表达式错误 “); return ERROR; /printf(“ 程序运行标志3n“); return OK; int main() BiTree T; Status St; char ch100,c; / 输
15、入的四则运算表达式char exp100; / 逆波兰表达式int count=0; int i=0; float result; printf(“ 请输入表达式: n“); while(i100) scanf(“%c“, chi+=c; if(c=n) ch-i=#; break; /end if CrtExptree(T, ch);/ 根据字符串ch 的内容构建表达式树T /后序遍历表达式树T 得到表达式的逆波兰表达式exp；count 中保存 exp 中字符的个数PostOrderTraverse(T, exp, count); printf(“ 逆波兰表达式为:n“); for(i=0; icount; i+) printf(“%c“,expi); printf(“n“); expcount = #; / 添加结束符St = evaluate (exp, result); / 计算逆波兰表达式exp 的值/输出计算的结果if
