《信息检索上机报告》

信息检索上机报告

信息储存与检索上机报告

姓名：马云学号：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（输入无效式子\nreturn（-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;k=2;）{

flag=0;

for（i=0;i=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（

copystr（rewrite（a），re）;

生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022输入1033或3234输入12与4243非5132存储227终止0

将表达式（a-b）*c+d变为检索指令的过程：地址检索词特征内容01a00102b00203c1—04d003检索词表1*0041+0。逆波兰输出区生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022非5123输入1031与4132输入1041或3123存储237终止0

将表达式（a-b）*c+d变为检索指令的过程：地址检索词特征内容01a00102b00203c1—04d003检索词表1*0041+0。逆波兰输出区生成的检索指令表为：操作码第一操作数第二操作数第三操作数输入1011输入1022非5123输入1031与4132输入1041或3123存储237终止0