搜索
信息储存与检索上机报告姓名：马云学号：06121001日期：2015.5.15（一）逆波兰变换一、上机题目：编写算法和程序，实现布尔检索式的逆波兰变换。二、试验编程语言：C语言三、程序设计总体思路：1、建立两个栈：算项指针栈和算符栈。2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：⑴如果是算项，将指向该算项的指针放到算项栈中。⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。⑶如果是运算符+-*,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒”。一棵表达式二叉树建立完成。3、后序遍历此二叉树，显示逆波兰表达式。四、程序源代码#includestdafx.h#includestdafx.h#includestdio.h#includestring.htypedefstruct{chars[20][20];inttop;}SQ;voidcopystr(char*a,char*b){inti=0;do{b[i]=a[i];i++;}while(a[i]!='\0');b[i]='\0';}voidvoidSQ(SQ*s){s-top=-1;}intifempty(SQ*s){return(s-top==-1);}voidpush(SQ*S,char*c){if(S-top==19)printf(overflow\n);else{S-top++;copystr(c,S-s[S-top]);}}char*pop(SQ*S){if(ifempty(S)){printf(overflow!\n);return(NULL);}elsereturn(S-s[S-top--]);}intjudge(char*c){if(c[1]=='\0')switch(c[0]){case'+':return(3);case'-':return(3);case'*':return(2);case'/':return(2);default:return(1);}elsereturn(1);}voidwrite(char*a,char*b,char*c){strcat(a,c);strcat(a,b);}intseek(char*c,intstart){intsignal=1;for(start=start++;c[start]!='\0'&&signal!=0;start++){if(c[start]==')')signal--;elseif(c[start]=='(')signal++;}if(signal==0)return(start-1);else{printf(输入无效式子\n);return(-1);}}voidFB(SQ*A,SQ*B){for(;!ifempty(A);){push(B,A-s[A-top]);pop(A);}}char*rewrite(char*A){SQfront;SQback;inti,j,k,flag=0;char*result;charmid[20];voidSQ(&front);voidSQ(&back);for(i=0;A[i]!='\0';){if(A[i]=='('){j=seek(A,i);for(k=i+1;kj;k++){mid[k-i-1]=A[k];}mid[j-i-1]='\0';copystr(rewrite(mid),mid);push(&back,mid);i=j+1;}elseif(A[i]!='('){mid[0]=A[i];mid[1]='\0';push(&back,mid);i++;}}FB(&back,&front);for(;front.top=2;){flag=0;for(i=0;i=front.top;i++){if(judge(front.s[i])==2){flag=1;break;}}if(flag==1){for(;front.top=2;){if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==2&&judge(front.s[front.top-2])==1){write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);push(&back,front.s[front.top]);pop(&front);pop(&front);pop(&front);}else{push(&back,front.s[front.top]);pop(&front);}}FB(&front,&back);FB(&back,&front);}else{for(;front.top=2;){if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==3&&judge(front.s[front.top-2])==1){write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);push(&back,front.s[front.top]);pop(&front);pop(&front);pop(&front);}else{push(&back,front.s[front.top]);pop(&front);}}FB(&front,&back);FB(&back,&front);}}result=front.s[front.top];return(result);}voidmain(){charre[20];chara[20];printf(请输入算式：\n);scanf(%s,a);copystr(rewrite(a),re);printf(逆波兰式：\n%s\n,re);}五、程序运行结果将中缀表达式：a*(b+(c-d))转换为逆波兰形式六、上机结果分析与总结（1）能够实现检索提问表达式的逆波兰形式输出，结果正确。（2）检索指令必须是精确匹配，友好性不是很好。（3）程序调试环境为Win-Tc,不能在中文DOS环境下运行，直观性差。（二）准波兰一、上机题目：编写算法和程序，实现布尔检索式的准波兰变换。二、试验编程语言：C语言三、程序设计总体思路：在逆波兰变换的基础上，进一步实现准波兰变换：（1）如上题程序中，建立前缀表达式的二叉树。（2）利用递归调用的思想，将每个节点左右子树的深度进行比较，如果右子树的深度大于左子树，将它们调换；如果小于或相等，则不动。（3）后序遍历打印二叉树，输出的即为准波兰表达式。如下图，即为二叉树变换为可以后序遍历生成准波兰表达式的树的过程：四、程序源代码//xinguan.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includeconio.h#includestdio.h#includestdlib.h#includestring.htypedefstructnode/*结构体*/{charchValue;structnode*pLeftChild,*pRightChild;/*指向左右节点的指针*/}BiNode;BiNode*GenerateTree(char*pFormula);/*由一般表达式生成树*/intDepthTree(BiNode*pRoot);voidChangeTree(BiNode*pRoot);voidPostOrderPrintTree(BiNode*pRoot);/*后续打印*/voidPostOrderFreeTree(BiNode*pRoot);/*释放节点*/voidmain(){charFormula[100],*a;BiNode*pRoot;printf(请输入算式:\n);a=Formula;scanf(%s,a);pRoot=GenerateTree(Formula);/*返回根节点的指针*/printf(\n);printf(准波兰式是:\n);ChangeTree(pRoot);PostOrderPrintTree(pRoot);PostOrderFreeTree(pRoot);printf(\n);getch();}unsignedcharIsOper(charop)/*判断是否为运算符*/{inti;charoper[]={'(',')','+','-','*','^'};for(i=0;isizeof(oper);i++){if(op==oper[i]){return1;}}return0;}intGetOperPri(charop)/*求运算符的优先级*/{switch(op){case'(':return1;case'+':case'-':return2;case'*':return3;case'.':return4;default:return0;}}staticcharOperStack[100];/*操作符栈*/staticBiNode*NodeStack[100];/*节点指针栈*/intOperLen=0;/*栈长度*/intNodeLen=0;PushOper(charop)/*压栈*/{OperStack[OperLen++]=op;}charPopOper()/*出栈*/{returnOperStack[--OperLen];}intSizeOper()/*栈长度,返回0表示空栈*/{returnOperLen;}charTopOper()/*栈顶元素*/{returnOperStack[OperLen-1];}PushNode(BiNode*no){NodeStack[NodeLen++]=no;}BiNode*PopNode(){returnNodeStack[--NodeLen];}intSizeNode(){returnNodeLen;}BiNode*GenerateTree(char*pFormula){BiNode*pNode;charch,c;intidx=0;ch=pFormula[idx++];while(0!=SizeOper()||'\0'!=ch){if('\0'!=ch&&!IsOper(ch))/*不是运算符，则算项进栈*/{pNode=(BiNode*)malloc(sizeof(BiNode));pNode-chValue=ch;pNode-pLeftChild=NULL;pNode-pRightChild=NULL;PushNode(pNode);ch=pFormula[idx++];}else{switch(ch){case'(':/*进栈*/PushOper('(');ch=pFormula[idx++];break;case')':/*脱括号*/while(1){c=PopOper();if('('==c)break;pNode=(BiNode*)malloc(sizeof(BiNode));pNode-chValue=c;pNode-pLeftChild=NULL;pNode-pRightChild=NULL;if(0!=SizeNode())pNode-pRightChild=PopNode();if(0!=SizeNode())pNode-pLeftChild=PopNode();PushNode(pNode);}ch