信息检索上机报告

信息储存与检索上机报告

姓名：马云学号：06121001日期：2015.5.15

（一）逆波兰变换

一、上机题目：

编写算法和程序，实现布尔检索式的逆波兰变换。

二、试验编程语言：c语言三、程序设计总体思路：

1、建立两个栈。算项指针栈和算符栈。

2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：

⑴如果是算项，将指向该算项的指针放到算项栈中。⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。

⑶如果是运算符+-*，将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈，作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒”。一棵表达式二叉树建立完成。

3、后序遍历此二叉树，显示逆波兰表达式。

四、程序源代码

#include\#include\#include#include

typedefstruct{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（\else{

s->top++;

copystr（c，s->s[s->top]）;}}

char*pop（sq*s）{

if（ifempty（s））{

printf（\return（null）;}else

return（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）;}else

return（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）;