pNode->chValue = ch;
pNode->pLeftChild = NULL; pNode->pRightChild = NULL; PushNode(pNode); ch = pFormula[idx++]; }
else {
switch(ch) {
case '(':/* 进栈 */ PushOper('(');
ch = pFormula[idx++]; 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())
pNode->pRightChild = PopNode(); if(0!=SizeNode())
pNode->pLeftChild = PopNode(); PushNode(pNode); }
ch = pFormula[idx++]; break; default:
if(0==SizeOper() || '\\0'!=ch && GetOperPri(TopOper()) < GetOperPri(ch)) { PushOper(ch);
ch=pFormula[idx++]; } else
{/* 出栈 */
pNode = (BiNode *)malloc(sizeof(BiNode)); pNode->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; }
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 ChangeTree(BiNode *pRoot) /* 如果右子树大于左子树，交换 */ {
BiNode *pTree=NULL; if(NULL != pRoot)
{if(DepthTree(pRoot->pLeftChild)
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(\ } } void PostOrderFreeTree(BiNode *pRoot) {
if(NULL != pRoot) {
PostOrderFreeTree(pRoot->pLeftChild); PostOrderFreeTree(pRoot->pRightChild); free(pRoot); } }
五、程序运行结果
六、上机结果分析与总结
（1）能够实现检索提问表达式的准波兰形式输出，结果正确。
（2）准波兰是对逆波兰变换的改进，在子树根不对称时，先处理较大分支，这样占用工作区较少。 （3）该方法算法稍微复杂，不过只在已有逆波兰检索系统上增加一个重组模块，可以将内存工作区从7个降低至5个。
（4）另外，在编程过程中，暴露出自己编程的知识还不够扎实。以后需加强。
（三）检索指令表
将表达式a+b*c-d变为检索指令的过程： 地址 检索词 特征 内容 01 a 0 01 02 b 0 02 03 c 0 03 04 d 1 * 检索词表 1 + 0 04 1 — 0 。 逆波兰输出区
生成的检索指令表为： 操作码 第一操作数 第二操作数 第三操作数 输入 1 01 1 输入 1 02 2 输入 1 03 3 与 4 2 3 4 或 3 1 4 2 输入 1 1 非 5 1 2 3 存储 2 3 7 终止 0 将表达式a-(b+c)*d变为检索指令的过程： 特征 内容 地址 检索词 0 01 01 a 0 02 02 b 0 03 03 c 1 + 04 d 0 04 检索词表 1 *
1 —
0 。
逆波兰输出区
生成的检索指令表为： 操作码 第一操作数 第二操作数 第三操作数 输入 1 01 1 输入 1 02 2 输入 1 03 3 或 3 2 3 4 输入 1 2 与 4 2 4 3 非 5 1 3 2 存储 2 2 7 终止 0
将表达式(a-b)*c+d变为检索指令的过程： 地址 检索词 特征 内容 01 a 0 01 02 b 0 02 03 c 1 — 04 d 0 03 检索词表 1 * 0 04 1 + 0 。 逆波兰输出区 生成的检索指令表为： 操作码 第一操作数 第二操作数 第三操作数 输入 1 01 1 输入 1 02 2 非 5 1 2 3 输入 1 03 1 与 4 1 3 2 输入 1 04 1 或 3 1 2 3 存储 2 3 7 终止 0