信息储存与检索上机报告
姓名：马云 学号：06121001 日期：2015.5.15
（一）逆波兰变换
一、上机题目：
编写算法和程序，实现布尔检索式的逆波兰变换。
二、试验编程语言：C语言 三、程序设计总体思路：
1、建立两个栈：算项指针栈和算符栈。
2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：
⑴如果是算项，将指向该算项的指针放到算项栈中。 ⑵如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（”以上的算符出栈。
⑶如果是运算符+ - *,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒” 。一棵表达式二叉树建立完成。
3、后序遍历此二叉树，显示逆波兰表达式。
四、程序源代码
#include \#include \#include
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(\ 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--]); }
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]!='\\0'&&signal!=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]!='\\0';) {
if(A[i]=='(') {
j=seek(A,i);
for(k=i+1;k { mid[k-i-1]=A[k]; } mid[j-i-1]='\\0'; copystr(rewrite(mid),mid); push(&back,mid); i=j+1; } else if(A[i]!='(') { mid[0]=A[i]; mid[1]='\\0'; 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(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