组合提交代码
#include<iostream>
#define MAXSIZE 100
using namespace std;
typedef struct BiTNode
{//二叉树的双链表存储表示
double data; //结点数据域
bool ischaracter; //判断结点是否为字符
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
typedef struct
{//字符栈的存储结构
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack1;
typedef struct
{//结点栈的存储结构
BiTree *base;
BiTree *top;
int stacksize;
}SqStack2;
void InitStack1(SqStack1 &s)
{//字符栈的初始化
s.base=new char[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
s.top=s.base; //初始为空栈
s.stacksize=MAXSIZE; //置栈的最大容量为MAXSIZE
}
void InitStack2(SqStack2 &s)
{//结点栈的初始化
s.base=new BiTree[MAXSIZE];
s.top=s.base;
s.stacksize=MAXSIZE;
}
void Push1(SqStack1 &s,char ch)
{//字符入栈操作
if(s.top-s.base==s.stacksize) //栈满
return;
*s.top=ch; //元素ch压入栈顶
s.top++; //栈顶指针加1
}
void Push2(SqStack2 &s,BiTree t)
{//结点入栈操作
if(s.top-s.base==s.stacksize)
return;
*s.top=t;
s.top++;
}
void Pop1(SqStack1 &s,char &ch)
{//字符出栈操作
if(s.top==s.base) //栈空
return;
else
{
s.top--; //栈顶指针减1
ch=*s.top; //将栈顶元素赋给ch
}
}
void Pop2(SqStack2 &s,BiTree &t)
{//结点出栈操作
if(s.top==s.base)
return;
else
{
s.top--;
t=*s.top;
}
}
char GetTop(SqStack1 s)
{//取字符栈的栈顶元素
if(s.base==s.top) //栈空
return -1;
else
return *(s.top-1); //返回栈顶元素的值，栈顶指针不变
}
bool EmptyStack(SqStack1 s)
{//栈的判空操作
if(s.base==s.top) //栈空返回true
return true;
else
return false; //栈非空返回false
}
char Precede(char a,char b)
{//判断符号的优先级
if(a=='+'||a=='-')
{
if(b=='+'||b=='-'||b==')'||b=='=')
return '>'; //>代表a的优先级高于b
else
return '<';
}
else if(a=='*'||a=='/')
{
if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='=')
return '>';
else
return '<';
}
else if(a=='(')
{
if(b==')')
return '=';
else
return '<';
}
else if(a==')')
return '>';
else
{
if(b=='=')
return '=';
else
return '<';
}
}
double Operate(double a,char ch,double b)
{//运算操作，返回相应的数值结果
if(ch=='+')
return a+b;
else if(ch=='-')
return a-b;
else if(ch=='*')
return a*b;
else
return a/b;
}
bool IsCharacter(char ch)
{//判断ch是否为+、-、*、/、(、)、= 这类的字符，是则返回true
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='=')
return true;
else
return false;
}
double InOrder(BiTree T)
{//中序遍历二叉树并求表达式的值
/**************begin************/
/**************end************/
}
void CreateBT(char ch[],BiTree &t,SqStack1 optr,SqStack2 expt)
{//创建二叉树
int i=0;
char opr,c[2]; //辅助数组c
BiTree t1,t2;
double num;
while(ch[i]!='\0'||!EmptyStack(optr))
{
if(!IsCharacter(ch[i])) //当前遍历的不是运算符元素
{
c[0]=ch[i];
c[1]='\0';
BiTree q=new BiTNode; //生成一个新结点*q
num=strtod(c,NULL); //将字符数组c转换成浮点数，赋给num
q->ischaracter=false; //结点*q不为运算符
q->data=num; //结点数据域置为num
q->lchild=NULL; //左右孩子置为NULL
q->rchild=NULL;
Push2(expt,q); //将结点q压入数字栈
i++; //指针i加1
}//if
else //当前遍历的是运算符元素
{
switch(Precede(GetTop(optr),ch[i])) //比较栈顶元素和当前遍历字符的优先级
{
case '<': //栈顶元素优先级小于当前运算符
Push1(optr,ch[i]); //将当前运算符入栈
i++; //指针i加1
break;
case '>': //栈顶元素优先级大于当前运算符
Pop1(optr,opr); //运算符栈的元素出栈
Pop2(expt,t2); //数字栈的栈顶元素出栈
Pop2(expt,t1);
t=new BiTNode; //生成新结点*t
t->ischaracter=true; //结点*t为运算符
t->data=opr; //结点数据域置为opr
t->lchild=t1; //左孩子指向t1
t->rchild=t2; //右孩子指向t2
Push2(expt,t); //将结点t压入数字栈
break;
case '=': //栈顶元素优先级等于当前运算符
Pop1(optr,opr); //运算符栈的元素出栈
i++; //指针i加1
break;
}//switch
}//else
}//while
}
int main()
{
char ch[MAXSIZE];
while(cin>>ch)
{
if(ch[0]=='=') break;
BiTree t;
SqStack1 optr; //运算符栈optr
SqStack2 expt; //数字栈expt
InitStack1(optr); //初始化栈
InitStack2(expt); //初始化栈
Push1(optr,'='); //先在运算符栈底放入一个'='
CreateBT(ch,t,optr,expt); //创建二叉树
double answer=InOrder(t);
cout<<answer<<endl;
}
return 0;
}
