利用二叉树求解表达式的值，编写程序test5.cpp
要求：输入一个算术表达式（以“#”开始，以“#”结束），建立对应的表达式树，输出表达式树的中序遍历序列，以验证表达式树是否建立正确，最后利用此表达式树求解表达式的值并输出。
分析：对于任意一个算术中缀表达式，都可用二叉树来表示。表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。因此问题的关键就是如何创建表达式树。
假设运算符均为双目运算符，则表达式对应的表达式树中叶子结点均为操作数，分支结点均为运算符。由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。这种处理方式见第3章表达式求值算法中的运算符的比较，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。
根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。可以另外借助一个表达式树栈，来暂存已建立好的表达式树的根结点，以便其作为另一个运算符结点的子树而被引用。
为实现表达式树的创建算法，可以使用两个工作栈，一个称为OPTR，用以暂存运算符；另一个称为EXPT，用以暂存已建立好的表达式树的根结点。为了便于实现，假设每个表达式均以“#”开始，以“#”结束。
（1） 表达式树的创建算法
① 初始化OPTR和EXPT，将表达式起始符“#”压入OPTR栈
② 扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR栈顶不为“#”时，则循环执行以下操作：
若ch不是运算符，则以ch为根创建一棵只有根结点的二叉树，且将该树根结点压入EXPT栈，读入下一个ch；
若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同处理：
小于，则ch压入OPTR栈，读入下一个ch；
大于，则弹出OPTR栈顶运算符，从EXPT栈弹出两个表达式子树的根结点，以该运算符为根结点，以弹出的第二个子树作为左子树，弹出的第一个子树为右子树，创建一棵新二叉树，并将该树根结点压入EXPT栈；
相等，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“（”，相当于括号匹配成功，然后读入下一个ch。
（2） 表达式树的求值
① 设变量lvalue和rvalue分别用以记录表达式树中左子树和右子树的值，初始均为0。
② 如果当前结点为叶子（结点为操作数），则返回该结点的数值，否则（结点为运算符）执行以下操作：
递归计算左子树的值记为lvalue；
递归计算右子树的值记为rvalue；
根据当前结点运算符的类型，将lvalue和rvalue进行相应运算并返回。
说明：表达式中的操作数简化为一位正整数。加分项：操作数可以是多位数，也可以是小数。
3、可自行查阅相关关于二叉树表示的求解表达式值的方法，设计相应算法。
//返回函数状态
typedef int Status;
typedef char ElemType;
//二叉树结构
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
}*BiTree;
//链栈结构
typedef struct StackNode {
ElemType data;
BiTree addr;
struct StackNode *next;
}*LinkStack;
class Stack {
public:
Status visit(ElemType e);
Status Init_Stack();
Status Empty_Stack();
Status Push_Stack_OPRT(ElemType e);
Status Push_Stack_EXRT(BiTree T_node);
ElemType Pop_Stack_OPRT();
BiTree Pop_Stack_EXPT();
Status Length_Stack();
ElemType Get_Stack();
Status Clear_Stack();
Status Traverse_Stack();
Status Destroy_Stack();
LinkStack top;
int count;
};
class Tree {
public:
Status visit(ElemType e);
//初始化二叉树T
Status InitBiTree();
//按先序遍历序列建立二叉链表T
Status CreateBiTree(BiTree T_node,char *str);
//检查二叉树T是否为空，空返回1，否则返回0
bool BiTreeEmpty();
//求二叉树T的深度并返回该值
int BiTreeDepth(BiTree T_node);
//先序遍历二叉树T
Status PreOrderTraverse(BiTree T_node);
//中序遍历二叉树T
Status InOrderTraverse(BiTree T_node);
//后序遍历二叉树T
Status PostOrderTraverse(BiTree T_node);
//销毁二叉树T
Status DestroyBiTree(BiTree T_node);
//建立数字二叉树
BiTree InitTree_Num(ElemType e);
//建立运算符二叉树
BiTree InitTree_Op(BiTree R_node,BiTree L_node,ElemType e);
//计算结果
double Result(BiTree T_node);
BiTree T;
};
#include "Resources.h"
#include "cal.h"
#include "LinkStack.h"
#include "Binary_Tree.h"
#include "Ui.h"
using namespace std;
int main() {
menu();
Tree tree;
Stack OPTR, EXPT;
ElemType e;
OPTR.Init_Stack();
OPTR.Push_Stack_OPRT('#');
EXPT.Init_Stack();
while (1) {
char ch;
ch = getchar();
if (ch == '#') {
OPTR.Destroy_Stack();
EXPT.Destroy_Stack();
tree.DestroyBiTree(tree.T);
system(SCREEN_CLS); //清屏
int i = 5;
while (i--) {
printf("计算器将在");
setColor(15, 0);
printf("%d", i);
setColor(10, 0);
printf("秒退出，感谢您的使用");
Sleep(1000);
system(SCREEN_CLS);
}
exit(0);
} else {
while (ch != '#' || OPTR.Get_Stack() != '#') {
if (ch >= '0' && ch <= '9') {
//将数字结点地址压入EXPT栈
EXPT.Push_Stack_EXRT(tree.InitTree_Num(ch));
ch = getchar();
} else {
//判断优先级
switch (Priority_Func(OPTR.Get_Stack(), ch)) {
case 1:
//获取字符
e = OPTR.Pop_Stack_OPRT();
//将运算符号地址压入EXPT栈
EXPT.Push_Stack_EXRT(
tree.InitTree_Op(EXPT.Pop_Stack_EXPT(),
EXPT.Pop_Stack_EXPT(), e));
break;
case 0://将运算符号弹出OPTR栈
OPTR.Pop_Stack_OPRT();
ch = getchar();
break;
case -1://将运算符号压入OPRT栈
OPTR.Push_Stack_OPRT(ch);
ch = getchar();
break;
default:
break;
}
}
}
tree.InitBiTree();
//获取根节点
tree.T = EXPT.Pop_Stack_EXPT();
printf("先 序 遍 历：");
tree.PreOrderTraverse(tree.T);
printf("\n");
printf("中 序 遍 历：");
tree.InOrderTraverse(tree.T);
printf("\n");
printf("后 序 遍 历：");
tree.PostOrderTraverse(tree.T);
printf("\nResult = %.2f\n", tree.Result(tree.T));
//清除缓存
fflush(stdin);
}
system("pause");
system(SCREEN_CLS);
menu2();
}
return 0;
}
