信息检索上机报告.doc

《信息检索上机报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息储存与检索上机报告姓名：马云学号：日期：2015.5.15（一）逆波兰变换一、上机题目：编写算法和程序，实现布尔检索式的逆波兰变换。二、试验编程语言：C语言三、程序设计总体思路：1、建立两个栈：算项指针栈和算符栈。2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：⑴如果是算项，将指向该算项的指针放到算项栈中。⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。⑶如果是运算符+-*,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈

2、栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒”。一棵表达式二叉树建立完成。3、后序遍历此二叉树，显示逆波兰表达式。四、程序源代码#include"stdafx.h"#include"stdafx.h"#include#includetypedefstruct{chars[20][20];inttop;}SQ;

3、voidcopystr(char*a,char*b){inti=0;do{b[i]=a[i];i++;}while(a[i]!='');b[i]='';}voidvoidSQ(SQ*s){s->top=-1;}intifempty(SQ*s){return(s->top==-1);}voidpush(SQ*S,char*c){if(S->top==19)printf("overflow");else{S->top++;copystr(c,S->s[S->top]);}}char*pop(SQ*S){if(ifempty(S)){prin

4、tf("overflow!");return(NULL);}elsereturn(S->s[S->top--]);}intjudge(char*c){if(c[1]=='')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(ch

5、ar*c,intstart){intsignal=1;for(start=start++;c[start]!=''&&signal!=0;start++){if(c[start]==')')signal--;elseif(c[start]=='(')signal++;}if(signal==0)return(start-1);else{printf("输入无效式子");return(-1);}}voidFB(SQ*A,SQ*B){for(;!ifempty(A);){push(B,A->s[A->top]);pop(A);}}char*re

6、write(char*A){SQfront;SQback;inti,j,k,flag=0;char*result;charmid[20];voidSQ(&front);voidSQ(&back);for(i=0;A[i]!='';){if(A[i]=='('){j=seek(A,i);for(k=i+1;k

7、id[1]='';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

8、(front.s[front.top],front.s[front.top-1],front.s[front.top-2]