中缀变后缀.txt

这个c语言程序实现中缀表达式变为后缀表达式

#include<string.h>
#include<stdio.h>
#define MAX 100					/*栈的最大容量*/
typedef struct
{
	int a[MAX];
	int top;
}stack;
typedef struct node
{
	int flag;				/*若该数为0则a表整数，否则a表运算符*/
	int a;					/*数据*/
	struct node *prior,*next;
}dlnode;
int relation[4][4]={{1,1,0,0},{1,1,0,0},{1,1,1,1},{1,1,1,1}};
int sumb(char a)				/*运算符付数值，以表示relation的下标*/				
{
	if(a=='+')
		return 0;
	if(a=='-')
		return 1;
	if(a=='*')
		return 2;
	if(a=='/')
		return 3;
}
int judge(char a,char b)			/*若a运算级别高返回1，b高返回0*/
{
	int i,j;
	i=sumb(a);
	j=sumb(b);
	return relation[i][j];
}
int count(int a,int b,char x)			/*计算a,b在x作用下的值*/
{
	if(x=='+')
		return a+b;
	if(x=='-')
		return a-b;
	if(x=='*')
		return a*b;
	if(x=='/')
		return a/b;
}
void h_insert(dlnode *head,int a,int flag)	/*向以head为头节点的链表中存入(a,flag)*/
{
	dlnode *p;
	p=(dlnode*)malloc(sizeof(dlnode));
	p->a=a;
	p->flag=flag;
	head->next->prior=p;
	p->prior=head;
	p->next=head->next;
	head->next=p;
}
void t_insert(dlnode *tail,int a,int flag)	/*向以tail为尾节点的链表中存入(a,flag)*/
{
	dlnode *p;
	p=(dlnode*)malloc(sizeof(dlnode));
	p->a=a;
	p->flag=flag;
	tail->prior->next=p;
	p->prior=tail->prior;
	p->next=tail;
	tail->prior=p;
}
stack *creatstack()				/*创建空栈*/
{
	stack *s;
	s=(stack*)malloc(sizeof(stack));
	s->top=0;
	return s;
}
int stackempty(stack *s)			/*判断栈空*/
{
	return s->top==0;
}
int stackfull(stack *s)				/*判断栈满*/
{
	return s->top==MAX-1;
}
void pushstack(stack *s,int a)			/*数a进栈*/
{
	if(stackfull(s))
	{
		printf("Too long!");
		exit(1);
	}
	else
		s->a[s->top++]=a;
}
int pops(stack *s)				/*返回栈顶元素，并出栈*/
{
	if(stackempty(s))
		return -1;
	else
		return s->a[s->top---1];
}
int squar(int a)				/*计算10的a次方*/
{
	int i,result=1;
	for(i=0;i<a;i++)
		result*=10;
	return result;
}
void Print(dlnode *head,dlnode *tail)		/*输出在以head为头tail为尾中的中缀表达式*/
{
	dlnode *p;
	for(p=head->next;p!=tail;p=p->next)
	{
		if(p->flag==0)
			printf("%d ",p->a);
		else
			printf("%c ",p->a);
	}
	printf("\n");
}
void main()
{
	int i=0,temp,c,m,j,i_t;
	int x,y,z,flag[MAX]={0};			/*flag为1表示对应的numstack中的数是计算出的，否则为新存的*/
	stack *numstack,*opstack;
	dlnode *head,*tail,*p;
	char list[200];					/*存放输入的表达式*/
	printf("Input list:");
	gets(list);
	head=(dlnode*)malloc(sizeof(dlnode));		/*开辟头尾节点以存放中缀表达式*/
	tail=(dlnode*)malloc(sizeof(dlnode));
	head->flag=head->a=tail->flag=tail->a=-1;
	tail->next=head->prior=NULL;
	tail->prior=head;
	head->next=tail;
	numstack=creatstack();				/*存放操作数*/
	opstack=creatstack();				/*存放运算符*/
	for(;(c=list[i])!='\0';i++)
	{
		if(c>='0'&&c<='9')			/*若遇到数值则存入numstack中*/
		{
			m=0;
			temp=0;
			while(c>='0'&&c<='9')
			{
				c=list[++i];
				m++;
			}
			i--;
			i_t=i;
			for(j=0;j<m;j++)
			{
				temp+=(list[i_t--]-48)*squar(j);
			}
			pushstack(numstack,temp);
		}
		else
		{
			if(c=='+'||c=='-'||c=='*'||c=='/')				/*若遇运算符*/
			{
				if(stackempty(opstack))
					pushstack(opstack,c);				/*运算符进opstack栈*/
				else
				{
					if(judge(opstack->a[opstack->top-1],c)==1)	/*若opstack栈顶元素运算级别高于刚进栈元素*/
					{
						do
						{
							x=pops(numstack);
							y=pops(numstack);
							z=pops(opstack);
							if(flag[numstack->top]==0&&flag[numstack->top+1]==0)	/*若顶上两元素都是新存的*/
							{
								t_insert(tail,y,0);
								t_insert(tail,x,0);				/*都加入链表尾*/
							}
							else
							{
								if(flag[numstack->top]==1&&flag[numstack->top+1]==0)		/*若最顶上的为计算出的*/
									h_insert(head,x,0);			/*最顶上的加入链表尾*/
								else
									if(flag[numstack->top]==0&&flag[numstack->top+1]==1)	/*若第二个为计算出的*/
										h_insert(head,y,0);		/*第二个加入链表尾*/
							}
							t_insert(tail,z,1);		/*取出的运算符加入链表*/		
							z=count(y,x,z);
							flag[numstack->top+1]=0;
							flag[numstack->top]=1;
							pushstack(numstack,z);		/*所得数值进栈numstack*/
						}while(judge(opstack->a[opstack->top-1],c)==1&&numstack->top>1);
					}
					pushstack(opstack,c);
				}
			}
			else								/*否则说明输错了字符*/
			{
				printf("You entered wrong char!\n");
				return;
			}
		}
	}
	if(numstack->top>1)					/*若numstack中还有数，则同上取出加入链表并计算数值*/
	{
		do
		{
			x=pops(numstack);
			y=pops(numstack);
			z=pops(opstack);
			if(flag[numstack->top]==0&&flag[numstack->top+1]==0)
			{
				t_insert(tail,y,0);
				t_insert(tail,x,0);
			}
			else
			{
				if(flag[numstack->top]==1&&flag[numstack->top+1]==0)
				{
					h_insert(head,x,0);
				}
				else
				{
					if(flag[numstack->top]==0&&flag[numstack->top+1]==1)
					{
						h_insert(head,y,0);
					}
				}
			}
			t_insert(tail,z,1);
			z=count(y,x,z);
			flag[numstack->top]=1;
			pushstack(numstack,z);
		}while(numstack->top>1);
	}
	printf("Backward: ");					/*输出后缀表达式*/
	Print(head,tail);
	if(stackempty(opstack)==1)				/*输出计算结果*/
		printf("Result:%d\n",numstack->a[numstack->top-1]);
	else
	{
		printf("Input wrong!\nMaybe a more operator!\n");
		exit(1);
	}
	printf("Press any key!");
	getch();
	for(p=head;p!=NULL;p=p->next)				/*释放存放中缀表达式的节点*/
		free(p);
}