一个表达式和一棵二叉树之间存在着自然的对应关系，请设计一个程序，实现基于二叉树表示的算术表达式的相关操作。主要包括前缀表达式构造二叉树，中缀表达式输出二叉树，对表达式中的变量分别赋值，后根遍历对表达式求值。

课程设计的基本要求

利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等) ;提高利用计算机分析解决综合性实际问题的基本能力。

具体要求如下:

1.对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理。

2、采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。学生也可根据自己对题目的理解增加新的功能模块(视情况可另外加分)。

3、系统以菜单界面方式(至少采用文本菜单界面，如能采用图形菜单界面更好)工作，运行界面友好，演示程序以用户和计算机的对话方式进行，利用文件进行数据的提取与存储。

4、程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强(能对错误输入进行判断控制)。

5、编程风格良好(包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等) ;

6、写出规范的课程设计报告，具体要求见相关说明文档。

课程设计的主要内容

题目描述: -个表达式和一-棵二叉树之间存在着自然的对应关系。请设计一个程序，实现基于二叉树表示的算术表达式的相关操作。

功能要求及说明:

假设算术表达式内可以含有变量(az),常量(09)和二元运算符(+,-,*,/) 。要求实现以下的操作:

(1) 以字符序列的形式输入语法正确的前缀表达式，并构造表达式二叉树;

(2) 用中缀表达式的形式输出表达式(在必要的地方添加()以正确反映运算的优先次序) ;

(3) 若表达式中含有变量，实现对表达式中的变量分别赋值;

(4)对算术表达式求值(用后根遍历的次序)，对含有变量的表达式，先对变量赋值，再计算表达式的值;

(5)采用模块化设计，分别以函数形式描述上述各功能。

测试数据

(1)不含变量的测例:分别输入0; -86;+-7*/93-645;并输出0; 8-6; 7-9/3*(6-4)+5;和计算结果0; 2; 6

(2) 对含有变量的表达式测例:分别输入a; +a*/b2a;并输出a; a+b/2*a; 分别给a,b赋不同的值(如a=3,b=4)， 计 算并分别输出表;达式的值(3; 9)。

(3)其它测例自选。