“前序算术表达式转换” 问题报告

“前序算术表达式转换”问题报告,小组名：Super star02计网5，6，7班,问题描述：算术表达式与二叉树 之间存在着对 应关系，一算法将先序形式输入的 合法算术表达式按中序方式输出。,基本要求：假设 算术表达式可以含有变量（ az）和二元运算符（+,-,*,/,（乘幂），实现下列功能：,(1)readExp(exp):从键盘读入一个合法的前序算 术表达式的字符串，并去除其 中的空格字符； (2)treeExp(exp): 根据合法的先序算术表达式建,立二叉树的存储结构，返回二叉树 的根结点指针；(3)printExp(exp):根据算术表达式的二叉树存储结 构，输出算术表达式的中序形式， 并能根据运算的优先级适当的加上 括弧；(4)freeTree(t):释放二叉树的存储空间。测试数据： （1）-a+bc； （2）/*abc （3）+a*b-cd （4）*/abc+def （5）*+ab-cd （6）-a-b-cd,算法思想：treeExp(exp)的算法思想是： 依次扫描先序表达式字符串exp，并以 扫描到的当前字符建立二叉树的结点 。若当前字符为变量，则该结点为叶 子结点，置左、右指针为空；若为运 算符，则递归调用 treeExp 建立该结点 的左子树和右子树。为了方便，可在 treeExp 函数中增加一个整形指针参数 ，以记录每次扫描的字符位置。Printexp(t)的算法描述是：,按二叉树的中序遍历序列输出各结点的值。当中序遍历输出左子树时，首先比较根结点和左孩子运算符的优先级，如果根结点运算符的优先级高于左孩子运算符的优先级，则在输出左子树时添加括号；当中序遍历输出右子树时，如果根结点运算符的优先级高于或等于有孩子运算符的优先级，则在输出右子树时添加括号。为此在该函数中调用了一个优先级计算函数opPriority，它返回字符的优先级，其返回值为： 1， 当c=+ 或+时 opPriority(c)= 2， 当c=*或c=/时 3， 当c=c时 4， 否则,算法实现,源程序# include # include # include #define maxNum 80Typedef struct BinNode char data: struct BinNode * Lchild,* Rchild; BinNode;Typedef BinNode *BinTree;,Void readExp(char exp) int i, j; printf(“输入前序算术表达式：” ,); while(* gets(exp)=0); i=j=0; while(expi!=0) / * 去除空格字符 */ if(expi!= ) i+; else expj+=expi+; expj=0;,BinTree treeExp(char exp,int *k) char ch; BinTree p; ch=exp(* k)+; / *扫描当前字符* / p=(BinTree)malloc(sizeof(BinNode); p-data=ch; / *建立当前字符的节点* / if(ch=a,Int opPriority(char c) if(c=+|c=-) return(1); if(c=*|c=/) return(2); if(c=) return(4);,Void printExp(BinTree t) int pri,pri1; char ch; ch=t-data; if(ch=a ,/*主程序*/Void main() Char ch,expmaxNum Int k; BinTree p; ch=Y; while(ch=Y|ch=y) readExp(exp); k=0; p=treeExp(exp, ,运行结果：输入前序算术表达式：-a+bc中序表达式为：a-(b+c)输入前序算术表达式：/ *abc中序表达式为：a*b/c输入前序算术表达式：+a * b-cb中序表达式为：a+b * (c-d),算法分析,本算法在建立二叉树时采用递归算法，在用中序遍历二叉树时用非递归的算法。空间