实验3四则运算表达式求值背景在工资管理软件中，不可避免的要用到公式的定义及求值等问题。
对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。
问题描述四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
基本要求使用二叉树来实现。
实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。
输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
选作内容（1）在输入输出方式上要求使用：输入：将中缀表达式存于文本文件中，程序从该文本文件中读出表达式。
输出：如果该中缀表达式正确，则将后缀表达式输出到该文件中原表达式的后面，它们之间用“---”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。
(2) 利用堆栈来实现中缀表达式转换为后缀表达式。
测试用例输入：21+23*（12-6）输出：21 23 12 6 -*+程序代码：#include <iostream>#include <string.h>using namespace std;#define SIZE 100#define STACKINCREMENT 10template<class T>//栈class stack{public:void InitStack() {S.base = (T *)malloc(SIZE * sizeof(T));if(!S.base) exit(0);S.top = S.base;S.stacksize = SIZE;}void DestroyStack(){free(S.base);}void ClearStack(){S.top = S.base;}bool StackEmpty(){if(S.top == S.base) return true;else return false;}int StackLength(){return (S.top - S.base);}bool GetTop(T &t){if(S.top != S.base){t = *(S.top - 1);return true;}else return false;}void Push(T t){if(S.top - S.base >= S.stacksize){S.base = (T *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(T));if(!S.base) exit(0);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top = t;S.top++ ;}bool Pop(T &t){if(S.top == S.base) return false;else S.top-- ;t = *S.top ;return true;}private:struct SqStack{T *base;T *top;int stacksize;}S;};class BiTree{private:struct BiTreeNode{char OPT[10];BiTreeNode *lchild,*rchild;};BiTreeNode *T; //T是根结点int index; //index是后缀表达式转换二叉树时的索引int number_of_point ;//销毁一颗树void DestroyTree(BiTreeNode *T){if(T){DestroyTree(T->lchild);DestroyTree(T->rchild);free(T);}}void DestroyTree(){DestroyTree(T);}//1表示栈顶优先级高于待入栈的元素int compare(char a,char b){ //定义了任意两个运算符的优先级if(a == '(' && b == ')') return 0;else if((a == '+' && b == '*') || (a == '+' && b == '/') || (a == '-' && b == '*') || (a == '-' && b == '/')|| (a != ')' && b == '(') || (a == '(' && b != ')'))return -1;else return 1;}//递归构造start,end分别是一个式子开始值和结束值的索引/*递归构造中缀表达式转化为的二叉树（利用栈） */void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end){ if(start == end) { //递归终止if(!(T = (BiTreeNode *)malloc(sizeof(BiTreeNode)))) exit(0);strcpy(T->OPT,str[start]);T->lchild = NULL;T->rchild = NULL;}else{stack<char> opt;stack<int> num;num.InitStack();opt.InitStack();char last;int index;int a;bool jump = false;for(int i = start;i <= end;i++) { //begin求解优先级最小的一个运算符if(jump) break;number_of_point = 0 ;if(IsNumber(str[i][0]) || str[i][0] == '-' &&IsNumber(str[i][1]) )continue;else{char c = str[i][0];char b;if(i == start && c == '(') {start += 1;continue;}else if(opt.StackEmpty() || (opt.GetTop(b) && compare(b,c) == -1)){opt.Push(c);num.Push(i);}else{if(c != ')'){opt.Pop(b);num.Pop(a);if(!opt.StackEmpty()){opt.GetTop(b);if(compare(b,c) == 1){opt.Pop(b);num.Pop(a);opt.Push(c);num.Push(i);}else{opt.Push(c);num.Push(i);}}else{opt.Push(c);num.Push(i);}}else{for(opt.GetTop(b);compare(b,c) != 0;opt.GetTop(b)){opt.Pop(b);num.Pop(a);if(opt.StackEmpty()){opt.Push(b);num.Push(a);end -= 1;jump =true;break;}}if(compare(b,c) == 0) {opt.Pop(b);num.Pop(a);}}}}} //end，得到的是该步中的根结点字符last及其索引indexopt.Pop(last);num.Pop(index);if(!opt.StackEmpty()){opt.Pop(last);num.Pop(index);}opt.DestroyStack();num.DestroyStack();if(!(T = (BiTreeNode *)malloc(sizeof(BiTreeNode)))) exit(0);T->OPT[0] = last;T->OPT[1] = '\0';InorderCreate(T->rchild,str,start,index-1);InorderCreate(T->lchild,str,index+1,end);}}bool IsNumber(char a){ //判断一个字符是否为数值形式的if( a == '.' && number_of_point == 0 ) {number_of_point ++ ;return true;}else if('0' <= a && a <= '9') return true ;else return false;}//递归求解树表示的表达式的值double Operate(BiTreeNode *T){if(T->lchild==NULL && T->rchild==NULL){double num = atof(T->OPT); //调用系统函数atof()将字符串转换为浮点数return num;}double ld,rd;ld = Operate(T->lchild);rd = Operate(T->rchild);char c = T->OPT[0];switch(c){case '+': return ld+rd;break;case '-': return rd-ld;break;case '*': return ld*rd;break;case '/': return rd/ld;break;default:cout << " you have entered wrong data ! "<< endl ;return 0;break ;}}void display(BiTreeNode *T){if(T == NULL ) return ;display(T->rchild);display(T->lchild);cout << T->OPT << " " ;public:BiTree() {T = NULL ;index = 0 ;number_of_point = 0 ;}/*以下两个函数重载私有成员函数方便计算*/void InorderCreate(){char OPT[30][10];cout << "输入中缀表达式: " << endl;char c = getchar();bool flag = true;int i = 0,j = 0 ;while(c != 10) { //输入的是空格j = 0;if(c == '-' && flag == true) { //flag判断是否是一个负数的值OPT[i][j++] = c;for(c = getchar() ; IsNumber(c) ; c = getchar() )OPT[i][j++] = c;OPT[i++][j] = '\0';flag = false;}else if(IsNumber(c)){OPT[i][j++] = c;for(c = getchar();IsNumber(c);c = getchar())OPT[i][j++] = c;OPT[i++][j] = '\0';flag = false;}else //运算符时的处理{flag = true;OPT[i][j++] = c;OPT[i++][j] = '\0';c = getchar();}}InorderCreate(T,OPT,0,i-1);}double Operate(){return Operate(T);}void display(){display(T) ;}~BiTree() {DestroyTree();};int main(){BiTree tree;tree.InorderCreate();cout << endl << tree.Operate() << endl;tree.display() ;cout << endl ;return 0;}测试结果：。
