1.如图二叉树表示下述表达式，a+b*(c-d)-e/f,若先序遍历此二叉树，按访问节点的顺序将节点排列起来，可达到二叉树的先序序列为，-+a*b-cd/ef。

2.对于此篇博文，我们要解决的问题，是如何通过表达式建立这个二叉树，并判断输入的序列是否正确，求出表达式的结果。

3.解决这个问题，大致分为3个部分

1. 将表达式进行转换成一个特定的链表，如图；
2. 将这个链表转换为一个二叉树
3. 求解二叉树。

 

 

 

 

 

#include<iostream>

#include<string>

#include<cctype>

using namespace std;

typedef struct Dtree

{

Dtree * lchild;

Dtree * rnchild;

char Date[12];

}PDtree;

int store(string temp, PDtree * & Shead);

int change (Dtree * & Shead);

void FreeTree(Dtree * &head);

int OperateT(Dtree * head,int & sign);

int deleteblank(string & temp);

int deal(Dtree * &head);

int liancheng(Dtree * &head);

int main()

{

int sign=1;

int value=1;

Dtree * Shead=NULL;

string oper;

cout<<"please the expression :"<<endl<<">>";

getline(cin,oper);

sign=store(oper,Shead);

if(sign==0)

{

cout<<"your input is error"<<endl;

goto end;

}

change(Shead);

value=OperateT(Shead,sign);

if(sign==2)

{

cout<<"the date you input is error"<<endl;

goto end;

}

cout<<"The value of expression is "<<value<<endl;

end:

FreeTree(Shead);

return 0;

}

int deleteblank(string & temp)

{

int i=0;

int j=0;

while(temp[i]==' '||temp[i]=='\t')

temp.erase(0,1);

j=temp.size()-1;

while(j>0&&(temp[j]==' '||temp[j]=='\t'))

{

temp.erase(j-1,1);

j=temp.size()-1;

}

temp.assign(temp.begin()+i,temp.end());

return 0;

}

int store(string temp,Dtree * & Shead)

{

int countdata=0;

int countop=0;

deleteblank(temp);

int length=temp.size();

while(length!=0&&temp[0]=='('&&temp[length-1]==')')

{

temp.assign(&temp[1],length-2);

deleteblank(temp);

length=temp.size();

}

if(length==0)

{

Shead=NULL;

return 0;

}

Shead=new Dtree;

Shead->lchild=NULL;

Shead->rnchild=NULL;

Dtree *temptree=Shead;

for(int i=0;i<length;)

{

if(temp[i]=='(')

{

++countdata;

if(countdata-countop!=1)

return 0;

++i;

int sign1=i;

int count=1;

while(i<length&&count!=0)

{

if(temp[i]=='(') ++count;

else if(temp[i]==')') --count;

++i;

if(count<0)

return 0;

}

if(count!=0)

return 0;

string temp2(temp,sign1,i-sign1-1);

deleteblank(temp2);

if(temp2.size()==0)

return 0;

sign1=store(temp2,temptree->lchild);

if(sign1==0)

return 0;

temptree->Date[0]=0;

}

else if(temp[i]==')')

return 0 ;

else if(isdigit(temp[i]))

{

++countdata;

if(countdata-countop!=1)

return 0;

int count=0;

while(i<length&&isdigit(temp[i])&&count<11)

{

temptree->Date[count]=temp[i];

++i;

++count;

}

temptree->Date[count]=0;

}

else if(temp[i]=='+'||temp[i]=='-'||temp[i]=='/'||temp[i]=='*')

{

++countop;

if(countop!=countdata)

return 0;

temptree->Date[0]=temp[i];

++i;

temptree->Date[1]=0;

}

else

return 0;

while((i<length)&&(temp[i]==' '||temp[i]=='\t'))

++i;

if(i==length) return 1;

else

{

temptree->rnchild=new Dtree;

temptree=temptree->rnchild;

temptree->lchild=NULL;

temptree->rnchild=NULL;

}

}

}

int change(Dtree * & Shead)

{

if(Shead->rnchild==NULL)

{

deal(Shead);

return 1;

}

Dtree * start=Shead;

Dtree * temp3=Shead;

Dtree * temp2=temp3->rnchild;

Dtree * temp1=temp2->rnchild;

int sign=0;

while(temp1)

{

if(temp2->Date[0]=='+'||temp2->Date[0]=='-')

{

temp3->rnchild=NULL;

liancheng(start);

if(sign==0)

{

sign=1;

Shead=temp2;

Shead->lchild=start;

}

else

{

Shead->rnchild=start;

temp3=Shead;

Shead=temp2;

Shead->lchild=temp3;

}

start=temp1;

temp3=temp1;

temp2=temp1->rnchild;

if(temp2==NULL)

break;

temp1=temp2->rnchild;

continue;

}

temp3=temp3->rnchild;

temp2=temp2->rnchild;

temp1=temp1->rnchild;

}

liancheng(start);

if(sign==0)

Shead=start;

else

Shead->rnchild=start;

return 1;

}

int deal(Dtree * & head)

{

if(head->Date[0]==0)

{

head=head->lchild;

change(head);

return 0;

}

else

{

head->lchild=NULL;

head->rnchild=NULL;

}

return 1;

}

//sign as a sign ,if sign==2,*/, if sign=1 ,+-,, if sign=0, head

int liancheng(Dtree * &head)

{

if(head->rnchild==NULL)

{

deal(head);

return 0;

}

Dtree *temp2=NULL;

Dtree * temp=head;

head=head->rnchild;

head->lchild=temp;

temp=head->rnchild->rnchild;

deal(head->lchild);

deal(head->rnchild);

while(temp)

{

temp2=head;

head=temp;

temp=temp->rnchild->rnchild;

head->lchild=temp2;

deal(head->rnchild);

}

return 1;

}

void FreeTree(Dtree * &head)

{

if(head==NULL) return;

else

{

FreeTree(head->lchild);

FreeTree(head->rnchild);

delete(head);

head=NULL;

}

}

int OperateT(Dtree * head,int & sign)

{

int left=0;

int right=0;

int value=1;

if(head->lchild==NULL)

return atoi(head->Date);

left=OperateT(head->lchild, sign);

if(sign==2) return 0;

right=OperateT(head->rnchild, sign);

if(sign==2) return 0;

if(head->Date[0]=='/'&&right==0)

{

sign=2;

return 0;

}

switch(head->Date[0])

{

case '+':

value=left+right;

break;

case '-':

value=left-right;

break;

case '*':

value=left*right;

break;

case '/':

value=left/right;

break;

default:

value=0;

}

return value;

}