信息检索上机报告教程.docVIP

信息储存与检索上机报告 姓名：马云 学号日期：2015.5.15 （一）逆波兰变换 一、上机题目： 编写算法和程序，实现布尔检索式的逆波兰变换。 二、试验编程语言：C语言 三、程序设计总体思路： 1、建立两个栈：算项指针栈和算符栈。 2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：  = 1 \* GB2 ⑴如果是算项，将指向该算项的指针放到算项栈中。  = 2 \* GB2 ⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。  = 3 \* GB2 ⑶如果是运算符+ - *,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒” 。一棵表达式二叉树建立完成。 3、后序遍历此二叉树，显示逆波兰表达式。 四、程序源代码 #include stdafx.h #include stdafx.h #includestdio.h #includestring.h typedef struct{char s[20][20];int top;}SQ; void copystr(char *a,char *b) { int i=0; do { b[i]=a[i]; i++; } while(a[i]!=\0); b[i]=\0; } void voidSQ(SQ *s) { s-top=-1; } int ifempty(SQ *s) { return(s-top==-1); } void push(SQ *S,char *c) { if(S-top==19) printf(over flow\n); else { S-top++; copystr(c,S-s[S-top]); } } char *pop(SQ *S) { if(ifempty(S)) { printf(over flow!\n); return(NULL); } else return(S-s[S-top--]); } int judge(char *c) { if(c[1]==\0) switch(c[0]) { case +:return(3); case -:return(3); case *:return(2); case /:return(2); default:return(1); } else return(1); } void write(char *a,char *b,char *c) { strcat(a,c); strcat(a,b); } int seek(char *c,int start) { int signal=1; for(start=start++;c[start]!=\0signal!=0;start++) { if(c[start]==)) signal--; else if(c[start]==() signal++; } if(signal==0) return(start-1); else { printf(输入无效式子\n); return(-1); } } void FB(SQ *A,SQ *B) { for(;!ifempty(A);) { push(B,A-s[A-top]); pop(A); } } char *rewrite(char *A) { SQ front; SQ back; int i,j,k,flag=0; char *result; char mid[20]; voidSQ(front); voidSQ(back); for(i=0;A[i]!=\