波兰变换算法.ppt

布尔检索 概念：布尔检索是用布尔逻辑运算符将检索词，短语或代码进行逻辑组配的一种技术。 布尔逻辑检索词: 或（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 。 检索词表 算子栈 （ + ） * 词表地址算子 。*++ 波兰法的转换 一般表示方法 正波兰表示方法 逆波兰表示方法 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 stdio.h #include stdlib.h #include string.h ? 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);