文档介绍：布尔检索
概念:布尔检索是用布尔逻辑运算符将检索词,短语或代码进行逻辑组配的一种技术。
布尔逻辑检索词: 或(or),与(and),非(no)。
三种逻辑检索词
A
A and B
B
A
B
A orB
No A B
布尔逻辑检索式的变换处理
1 逆波兰变换法(福岛法) 逆波兰表达式是一种没有括号,严格遵循从左到右运算的后缀表达方式。例如,逻辑提问方式“A*(B+C)+D”转换成逆波兰变化是“ABC+*D+”,这使得检索更加方便,但需要提问式的转换。
运算符优先级:—》* 》+ 》( ,)
2 三个存储区:
算子栈:用于存放转换过程中的运算符
检索词表储存区:存放检索词
逆波兰输出区:存放逻辑提问式的波兰表达方式
3 转换的处理方式
遇运算符:若当前的算符优先级高于前一运算符,把该运算符送到算子栈内,否则,将顶部算符取出送到逆波兰输出区。
波兰变换理论
遇左括号:表示其后存在一个复合检索项,暂不组成运算。应将左括号无条件至于算子栈内。
遇右括号:表示其与左括号之间的所有运算符都可以构成运算,栈内括号间的所有运算符无条件的出栈,并送逆波兰输出区,同时放弃掉这对括号。
遇运算项:将运算项检索词存入检索表,并将其在检索词表的位置送到波兰输出区
遇结束号:算子栈内的算子依次出栈到逆波兰输出区
算子栈的元素后进先出,转换结束其算子的栈为空,逆波兰的输出区为特征1,检索词为0,见下图
(A+B)*(C+EF)
逻辑提问方式
地址
检索词
01
A
02
B
03
C
04
EF
特征
内容
0
01
0
02
1
+
0
03
0
04
1
+
1
*
0
。
检索词表
算子栈
(
+
)
*
词表地址
04030201
算子
。*++
波兰法的转换
一般表示方法
正波兰表示方法
逆波兰表示方法
A+B* C
+A* BC
ABC* +
A+B * C+D
*+AB+CD
AB+CD+*
A+B*C+D-E*F
+*+ABC*-DEF
AB+C*DE-F*+
波兰变换的实现
1、建立两个栈:算项指针栈和算符栈。
2、将表达式送入表达式数组,从左向右扫描检索提问表达式中的字符,对当前字符做如下处理:
⑴如果是算项,将指向该算项的指针放到算项栈中。
⑵如果是“(”,则“(”无条件进算符栈,如果是“)”,则将算符栈中“(”以及“(”以上的算符出栈。
⑶如果是运算符+ - *,将他们与算符栈栈顶算符进行比较,如果优先级高于那个算符,将此算符进栈。如果低于算符栈栈顶算符,则把那个算符作为树的根节点。这时算项栈栈顶指针出栈,其所指字符作为右孩子,再将此时算项栈栈顶指针出栈,作为该根节点的左孩子;再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“﹒”。一棵表达式二叉树建立完成。
3、后序遍历此二叉树,显示逆波兰表达式。
#include <>
#include <>
#include <>
 
typedef struct node /* 结构体*/
{
char chValue;
struct node *pLeftChild, *pRightChild; /* 指向左右节点的指针*/
} BiNode;
 
BiNode *GenerateTree(char *pFormula); /* 由一般表达式生成树*/
void PostOrderPrintTree(BiNode *pRoot); /* 后续打印*/
void PostOrderFreeTree(BiNode *pRoot); /* 释放节点*/
 
void main()
{ char Formula[100],*a;
BiNode *pRoot;
printf("&& the process of changing profix expression into postfix expression&&\n");
printf(" deviser:Chenlonglong \n");
printf("Please input the profix expression\n");
a=Formula;
scanf("%s",a);
pRoot = GenerateTree(Formula);/* 返回根节点的指针*/
printf("The postfix expression is:\n");
PostOrderPrintTree(pRoot);
 
printf("\n");
getch();
}
unsig