数据结构考研分类复习真题 第六章 答案 (五)[3]

．[题目分析]首先通过对二叉树后序遍历形成后缀表达式这可通过全局变量的字符数组存放后缀表达式接着对后缀表达式求值借助于一栈存放运算结果从左到右扫描后缀表达式遇操作数就压入栈中遇运算符就从栈中弹出两个操作数作运算符要求的运算并把运算结果压入栈中如此下去直到后缀表达式结束这时栈中只有一个数这就是表达式的值

char ar[maxsize];//maxsize是后缀表达式所能达到的最大长度

int i=;

void PostOrder(BiTree t )//后序遍历二叉树t以得到后缀表达式

{if(t)

{PostOrder(t>lchild); PostOrder(b>rchild)ar[i++]=b>data; }

}//结束PostOrder

void EXPVALUE()

//对二叉树表示的算术表达式进行后缀表达式的求值

{ar[i]=\; //给后缀表达式加上结束标记

char value[]; //存放操作数及部分运算结果

i=; ch=ar[i++];

while(ch!=\)

{switch(ch)

{case ch in op: opnd=pop(value);opnd=pop(value); //处理运算符

push(operate(opndchopnd));break;

default: push(valuech); //处理操作数压入栈中

}

ch=ar[i++]; //读入后缀表达式

} printf(value[]); //栈中只剩下一个操作数即运算结束

} //结束EXPVALUE

[算法讨论] 根据题意操作数是单字母变量存放运算结果的栈也用了字符数组实际上操作数既可能是变量也可以是常量运算中两个操作数（opnd 和opnd）也不会直接运算即两个操作数要从字符转换成数（如是字符而数值=）数在压入字符栈也必须转换算法中的operate也是一个需要编写的函数可参见上面算法设计题其细节不再深入讨论

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []