树的多项式表达.cpp

树的多项式表达

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
#include<string.h>

struct stacknode//存每一个输入的字符（有数字，有计算符和括号）
{
	char a;
	int signal;//指示符号的优先级  
	stacknode *ptr;
};

struct stack//存经过处理之后的操作数
{
	int score;
	stack *ptr;
};

struct node
{
	int parent;
	int lchild;
	int rchild;
	int a;
	char s;
	bool op;
}treenode[1024];

int flag=0;
int q=0;
char a[128];

typedef stacknode STACK;
typedef STACK* STACKPTR;

int transform(char *,int,STACKPTR*);
void takel(STACKPTR);//堆栈内容按括号分区
void pop(STACKPTR*);
void push(STACKPTR,char,int);
int pop1(stack **);
void push1(stack*,int);
void op(stack **,char);
int strtoint(char *,int);
int tree(void);
void show(int);
void calculate(void);


int main()
{
	char s[128];
	int i=0;
	STACKPTR top;
	int k;

	do{
		printf("输入表达式按回车结束！\n");

		top=new STACK;
		top->ptr=NULL;

		memset(s,0,sizeof(s));
		scanf("%s",s);

		while(s[i]!='\0')
			i++;
		printf("后缀表达式为:\n");
		transform (s,0,&top);
		printf("\n");

		k=tree();
		printf("树结构表达式为:\n");
		show(k);
		calculate();

		delete top;
		
		printf("是否继续？(y or n)\n");
		while(getchar()!='\n');

		scanf("%c",&s[0]);
	}while(s[0]=='y');

	
	return 0;
}


int transform (char *s,int i,STACKPTR * top1)
{
	int k=0,temp=0,m=0,z=0;
	STACKPTR top;
	top=*top1;
	
	while(s[i]!=')'&&s[i]!='\0')
	{
		if(s[i]=='(')
		{
			takel(top);
			i=transform (s,++i,&top);
		}
		if(s[i]==')'||s[i]=='\0')
			break;
		if(isdigit(s[i]))
		{
			if(flag==1)
			{
				if(isdigit(s[i+1])&&k==0)//判断输入字符是否为多位数的开头字符。
				{	
					printf("(");
					a[q++]='(';
					k=1;			
				}
				printf("%c",s[i]);
				a[q++]=s[i];
				
				if(!isdigit(s[i+1]))
				{
					if(isdigit(s[i-1])&&k==1)//判断输入字符是否为多位数的最后数字。
					{
						printf(")");
						a[q++]=')';
						k=0;
					}
				}
			}
			else
			{
				if(isdigit(s[i+1]))
				{	
					printf("(");
					a[q++]='(';
					k=1;
				}
				printf("%c",s[i]);
				a[q++]=s[i];
				flag=1;
			}
		}
		else
		{	
			if(s[i]=='*'||s[i]=='/')
				temp=1;
			if(s[i]=='+'||s[i]=='-')
				temp=0;
			if(top->ptr==NULL)
				push(top,s[i],temp);
			else
			{			
				if(top->ptr->signal<temp)
					push(top,s[i],temp);
				else
				{
					while(top->ptr!=NULL)
					{
						if(top->ptr->signal>=temp)
							pop(&top);
						else
							break;
					}
					push(top,s[i],temp);
				}
			}
		}
		i++;	
	}
	while(top->ptr!=NULL&&top->ptr->signal!=-1) 
		pop(&top);
	*top1=top->ptr;
	
	return ++i;
}

int tree()
{
	int i,k=0,n=0;
	int j=0;
	char s[32];
	int b[32];

	for(i=0;i<q;i++)
	{
		if(isdigit(a[i]))
		{
			treenode[j].op=0;
			treenode[j].a=((int)a[i]-48);

		}
		else
			if(a[i]=='(')
			{
				i++;
				k=0;
				while(a[i]!=')')
					s[k++]=a[i++];
				treenode[j].a=strtoint(s,k-1);
				treenode[j].op=0;
			}
			else
			{
				treenode[j].s=a[i];
				treenode[j].op=1;
			}
			treenode[j].parent=-1;
			treenode[j].lchild=-1;
			treenode[j].rchild=-1;
			j++;
	}

	for(i=0;i<j;i++)
	{
		if(treenode[i].op==0)
			b[n++]=i;
		else
		{
			treenode[i].lchild=b[--n];
			treenode[b[n]].parent=i;
			treenode[i].rchild=b[--n];
			treenode[b[n]].parent=i;
			b[n++]=i;
		}			
	}

	return i-1;

}

void show(int n)
{ 
		printf("%c(",treenode[n].s);
	if(treenode[treenode[n].lchild].op==0)
		printf("%d,",treenode[treenode[n].lchild].a);
	else
	{
		show(treenode[n].lchild);
		printf(",");
	}
	
	if(treenode[treenode[n].rchild].op==0)
		printf("%d)",treenode[treenode[n].rchild].a);
	else
	{
		show(treenode[n].rchild);
		printf(")");
	}
}

void calculate(void)
{
	int i=0,j=0,k=0,score=0;
	char temp[16];
	int b=0;

	stack * numptr;
	numptr= new stack;
	numptr->ptr=NULL;

	while(a[i]!='\0')
	{
		if(isdigit(a[i]))
		{
			b=(int)a[i]-48;
			push1(numptr,b);
			j++;
		}
		else
		{
			if(a[i]=='(')
			{
				i++;
				k=0;
				while(a[i]!=')')
				{
					temp[k++]=a[i++];
				}
				b=strtoint(temp,k-1);
				push1(numptr,b);
			}
			else
			op(&numptr,a[i]);			
		}
		i++;
	}

	printf("表达式求值结果:\n");
	printf("%d\n",pop1(&numptr));

}


void pop(STACKPTR* top)
{
	STACKPTR newptr;
		
	newptr=*top;
		
	printf("%c",newptr->ptr->a);
	a[q++]=newptr->ptr->a;
	*top=newptr->ptr;
	
	delete newptr;
	
	return; 	
}

void push(STACKPTR top,char temp,int k)
{
	STACKPTR newptr;
	newptr=new STACK;
	
	newptr->a=temp;
	newptr->signal=k;
	newptr->ptr=top->ptr;  
	top->ptr=newptr;
	
	return ;
}

void takel(STACKPTR top)
{
	STACKPTR newptr;
	newptr=new STACK;

	newptr->signal=-1;
	newptr->ptr=top->ptr;
	top->ptr=newptr;

	return;
} 

void push1(stack* numptr,int b)
{
	stack * newptr;
	newptr=new stack;

	newptr->score=b;
	newptr->ptr=numptr->ptr;

	numptr->ptr=newptr;

	return;
}

int pop1(stack** numptr)
{
	stack * newptr;
	
	newptr=*numptr;

	*numptr=newptr->ptr;

	return newptr->ptr->score;
	
}

void op(stack** numptr,char oper)
{
	int a=0,b=0;
	int score=0;
	a=pop1(numptr);
	b=pop1(numptr);
	if(oper=='+')
		score=a+b;
	if(oper=='-')
		score=b-a;
	if(oper=='*')
		score=a*b;
	if(oper=='/')
		score=b/a;

	push1(*numptr,score);

	return;
	
}


int strtoint(char * s,int k)
{
	int b=k,score=0,i=0;
	int n=0;

	for(;b>=0;b--,n++)
	{
		n=int(s[i++])-48;
		n=(int)pow(10,b)*n;
		score=score+n;
	}

	return score;
}