信息检索上机报告信息储存与检索上机报告姓名：马云学号：06121001日期：2015.5.15（一）逆波兰变换一、上机题目：编写算法和程序，实现布尔检索式的逆波兰变换。二、试验编程语言：c语言三、程序设计总体思路：1、建立两个栈。算项指针栈和算符栈。2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：⑴如果是算项，将指向该算项的指针放到算项栈中。⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。⑶如果是运算符+-*，将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈，作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒”。一棵表达式二叉树建立完成。3、后序遍历此二叉树，显示逆波兰表达式。四、程序源代码include\Xinclude\XincludeXincludetypedefstruct{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）{第1页共7页return（s->top==-1）;}voidpush（sq*s，char*c）{if（s->top==19）printf（\else{s->top++;copystr（c，s->s[s->top]）;}}char*pop（sq*s）{if（ifempty（s））{printf（\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;第2页共7页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;k=2;）{flag=0;for（i=0;i=2;）{if（judge（front.s[front.top]）==1judge（front.s[front.top-1]）==2judge（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]）==1judge（front.s[front.top-1]）==3judge（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（\copystr（rewrite（a），re）;第3页共7页printf（\逆波兰式：\\n%s\\n\}五、程序运行结果将中缀表达式：a*（b+（c-d））转换为逆波兰形式六、上机结果分析与总结（1）能够实现检索提问表达式的逆波兰形式输出，结果正确。（2）检索指令必须是精确匹配，友好性不是很好。（3）程序调试环境为win-tc，不能在中文dos环境下运行，直观性差。（二）准波兰一、上机题目：编写算法和程序，实现布尔检索式的准波兰变换。二、试验编程语言：c语言三、程序设计总体思...
