{
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); }
void main() {
char re[20]; char a[20];
printf(\请输入算式：\\n\
scanf(\
copystr(rewrite(a),re);
printf(\逆波兰式：\\n%s\\n\
}
五、程序运行结果
将中缀表达式：a*(b+(c-d))转换为逆波兰形式
六、上机结果分析与总结
（1）能够实现检索提问表达式的逆波兰形式输出，结果正确。 （2）检索指令必须是精确匹配，友好性不是很好。
（3）程序调试环境为Win-Tc,不能在中文DOS环境下运行，直观性差。
（二）准波兰
一、上机题目：
编写算法和程序，实现布尔检索式的准波兰变换。
二、试验编程语言：C语言 三、程序设计总体思路：
在逆波兰变换的基础上，进一步实现准波兰变换： （1） 如上题程序中，建立前缀表达式的二叉树。 （2） 利用递归调用的思想，将每个节点左右子树的深度进行比较，如果右子树
的深度大于左子树，将它们调换；如果小于或相等，则不动。 （3） 后序遍历打印二叉树，输出的即为准波兰表达式。
如下图，即为二叉树变换为可以后序遍历生成准波兰表达式的树的过程：
四、程序源代码
// xinguan.cpp : Defines the entry point for the console application. //
#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 PostOrderFreeTree(BiNode *pRoot); /* 释放节点 */ void main()
{ char Formula[100],*a; BiNode *pRoot;
printf(\请输入算式:\\n\ a=Formula; scanf(\
pRoot = GenerateTree(Formula);/* 返回根节点的指针 */ printf(\ printf(\准波兰式是:\\n\ ChangeTree(pRoot);
PostOrderPrintTree(pRoot); PostOrderFreeTree(pRoot); printf(\ getch(); }
unsigned char IsOper(char op) /* 判断是否为运算符 */ {
int i;
char oper[] = {'(', ')', '+', '-', '*', '^'}; for(i=0; i if(op==oper[i]) { return 1; } } return 0; } int GetOperPri(char op) /* 求运算符的优先级 */ { switch(op) { case '(': return 1; case '+': case '-': return 2; case '*': return 3; case '.': return 4; default: return 0; } } static char OperStack[100]; /* 操作符栈 */ static BiNode *NodeStack[100]; /* 节点指针栈 */ int OperLen = 0; /* 栈长度 */ int NodeLen = 0; PushOper(char op) /* 压栈 */ { OperStack[OperLen++] = op; } char PopOper() /* 出栈 */ { return OperStack[--OperLen]; } int SizeOper() /* 栈长度, 返回0表示空栈 */ { return OperLen; } char TopOper() /* 栈顶元素 */ { return OperStack[OperLen-1]; } PushNode(BiNode *no) { NodeStack[NodeLen++] = no; } BiNode *PopNode() { return NodeStack[--NodeLen]; } int SizeNode() { return NodeLen; } BiNode *GenerateTree(char *pFormula) { BiNode *pNode; char ch,c; int idx = 0; ch = pFormula[idx++]; while(0!=SizeOper() || '\\0'!=ch) { if('\\0'!=ch && !IsOper(ch)) /* 不是运算符，则算项进栈*/ { pNode = (BiNode *)malloc(sizeof(BiNode));