波兰变换算法

1、布尔检索概念：布尔检索是用布尔逻辑运算符将检索词，短语或代码进行逻辑组配的一种技术。布尔逻辑检索词: 或（or），与（and），非（no）。三种逻辑检索词AA and B BAB A orB No A B 布尔逻辑检索式的变换处理 1 逆波兰变换法（福岛法） 逆波兰表达式是一种没有括号，严格遵循从左到右运算的后缀表达方式。例如，逻辑提问方式“A*（B+C）+D”转换成逆波兰变化是“ABC+*D+”，这使得检索更加方便，但需要提问式的转换。运算符优先级：* + （ ，） 2 三个存储区：算子栈：用于存放转换过程中的运算符检索词表储存区:存放检索词逆波兰输出区：存放逻辑提问式的波兰表达方式 3 转

2、换的处理方式遇运算符：若当前的算符优先级高于前一运算符，把该运算符送到算子栈内，否则，将顶部算符取出送到逆波兰输出区。波兰变换理论 遇左括号：表示其后存在一个复合检索项，暂不组成运算。应将左括号无条件至于算子栈内。 遇右括号：表示其与左括号之间的所有运算符都可以构成运算，栈内括号间的所有运算符无条件的出栈，并送逆波兰输出区，同时放弃掉这对括号。 遇运算项：将运算项检索词存入检索表，并将其在检索词表的位置送到波兰输出区 遇结束号：算子栈内的算子依次出栈到逆波兰输出区 算子栈的元素后进先出，转换结束其算子的栈为空，逆波兰的输出区为特征1，检索词为0，见下图（A+B）*（C+EF）逻辑提问方式地址检

3、索词01A02B03C04EF特征内容0010021+0030041+1*0。检索词表算子栈（ + ） *词表地址04030201算子。*+波兰法的转换一般表示方法正波兰表示方法 逆波兰表示方法A+B* C+A* BCABC* +A+B * C+D*+AB+CDAB+CD+*A+B*C+D-E*F+*+ABC*-DEFAB+C*DE-F*+波兰变换的实现1、建立两个栈：算项指针栈和算符栈。2、将表达式送入表达式数组，从左向右扫描检索提问表达式中的字符，对当前字符做如下处理：如果是算项，将指向该算项的指针放到算项栈中。如果是“（”，则“（”无条件进算符栈，如果是“）”，则将算符栈中“（”以及“（

4、”以上的算符出栈。如果是运算符+ - *,将他们与算符栈栈顶算符进行比较，如果优先级高于那个算符，将此算符进栈。如果低于算符栈栈顶算符，则把那个算符作为树的根节点。这时算项栈栈顶指针出栈，其所指字符作为右孩子，再将此时算项栈栈顶指针出栈,作为该根节点的左孩子；再将指向该根节点的指针入算项栈。也就是将此时的这棵树作为了一个算项。如此循环直到表达式数组最后一个运算符为终止符“” 。一棵表达式二叉树建立完成。3、后序遍历此二叉树，显示逆波兰表达式。#include #include #include typedef struct node /* 结构体 */ char chValue; struct

5、 node *pLeftChild, *pRightChild; /* 指向左右节点的指针 */ BiNode; BiNode *GenerateTree(char *pFormula); /* 由一般表达式生成树 */void PostOrderPrintTree(BiNode *pRoot); /* 后续打印 */void PostOrderFreeTree(BiNode *pRoot); /* 释放节点 */ void main() char Formula100,*a; BiNode *pRoot; printf(& the process of changing profix

6、 expression into postfix expression&n); printf( deviser:Chenlonglong n); printf(Please input the profix expressionn); a=Formula; scanf(%s,a); pRoot = GenerateTree(Formula);/* 返回根节点的指针 */ printf(The postfix expression is：n); PostOrderPrintTree(pRoot); printf(n); getch(); unsigned char IsOper(char

7、 op) /* 判断是否为运算符 */ int i; char oper = (, ), +, -, *, ; for(i=0; ichValue = ch; pNode-pLeftChild = NULL; pNode-pRightChild = NULL; PushNode(pNode); ch = pFormulaidx+; else switch(ch) case (: PushOper(); /* “(”无条件进栈 */ ch = pFormulaidx+; break; case ): /* 脱括号 */ while(1) c = PopOper(); if(=c) break;

8、pNode = (BiNode *)malloc(sizeof(BiNode); pNode-chValue = c; pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(0!=SizeNode() pNode-pRightChild = PopNode(); if(0!=SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode); ch = pFormulaidx+; break; default: if(0=SizeOper() | 0!=ch & GetOperPri(T

9、opOper() chValue = PopOper(); pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(SizeNode() pNode-pRightChild = PopNode(); if(SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode); /* PopOper(); */ break; pNode = PopNode(); /* 树的根节点 */ return pNode; void PostOrderPrintTree(BiNode *pRoot) /* 后序

10、遍历打印二叉树*/ if(NULL != pRoot) PostOrderPrintTree(pRoot-pLeftChild); PostOrderPrintTree(pRoot-pRightChild); printf(%c, pRoot-chValue); void PostOrderFreeTree(BiNode *pRoot) /* 后序遍历释放二叉树*/ if(NULL != pRoot) PostOrderFreeTree(pRoot-pLeftChild); PostOrderFreeTree(pRoot-pRightChild); free(pRoot); #include

11、#include #include typedef struct node /* 结构体 */ char chValue; struct node *pLeftChild, *pRightChild; /* 指向左右节点的指针 */ BiNode; BiNode *GenerateTree(char *pFormula); /* 由一般表达式生成树 */int DepthTree(BiNode *pRoot);void ChangeTree(BiNode *pRoot);void PostOrderPrintTree(BiNode *pRoot); /* 后续打印 */void PostOrd

12、erFreeTree(BiNode *pRoot); /* 释放节点 */ void main() char Formula100,*a; BiNode *pRoot; printf(& the process of changing profix expression into ZHUN expression &n); printf( deviser:Chenlonglong nnnn); printf(Please input the profix expression:n); a=Formula; scanf(%s,a); pRoot = GenerateTree(For

13、mula);/* 返回根节点的指针 */ printf(n); printf(The ZHUN expression is:n); ChangeTree(pRoot); PostOrderPrintTree(pRoot); PostOrderFreeTree(pRoot); printf(n); getch(); unsigned char IsOper(char op) /* 判断是否为运算符 */ int i; char oper = (, ), +, -, *, ; for(i=0; ichValue = ch; pNode-pLeftChild = NULL; pNode-pRight

14、Child = NULL; PushNode(pNode); ch = pFormulaidx+; else switch(ch) case (:/* 进栈 */ PushOper(); ch = pFormulaidx+; break; case ):/* 脱括号 */ while(1) c = PopOper(); if(=c) break; pNode = (BiNode *)malloc(sizeof(BiNode); pNode-chValue = c; pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(0!=SizeNode

15、() pNode-pRightChild = PopNode(); if(0!=SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode); ch = pFormulaidx+; break; default: if(0=SizeOper() | 0!=ch & GetOperPri(TopOper() chValue = PopOper(); pNode-pLeftChild = NULL; pNode-pRightChild = NULL; if(SizeNode() pNode-pRightChild = PopNode();

16、 if(SizeNode() pNode-pLeftChild = PopNode(); PushNode(pNode); /* PopOper(); */ break; pNode = PopNode(); /* 根节点 */ return pNode; int DepthTree(BiNode *pRoot) /* 树深度 */ int l,r; if(pRoot=NULL)return 0; l=DepthTree(pRoot-pLeftChild); r=DepthTree(pRoot-pRightChild); return(l=r? l+1:r+1); void ChangeTre

17、e(BiNode *pRoot) /* 如果右子树大于左子树，交换 */ BiNode *pTree=NULL; if(NULL != pRoot) if(DepthTree(pRoot-pLeftChild)pRightChild) pTree=pRoot-pRightChild; pRoot-pRightChild=pRoot-pLeftChild; pRoot-pLeftChild=pTree; ChangeTree(pRoot-pLeftChild); ChangeTree(pRoot-pRightChild); void PostOrderPrintTree(BiNode *pRoot) if(NULL != pRoot) PostOrderPrintTree(pRoot-pLeftChild); PostOrderPrintTree(pRoot-pRightChild); printf(%c, pRoot-chValue); void PostOrderFreeTree(BiNode *pRoot) if(NULL != p