逆波兰式.c

逆波兰式的算法实现

#include<stdio.h>
#include<malloc.h>
typedef struct node
{
	char data;
	struct node *next;
}node,*stack;
char A[7]={'+','-','*','/','^','(',')'};
char yxjz[7][7]={{'>','>','<','<','<','<','>'},{'>','>','<','<','<','<','>'},{'>','>','>','>','<','<','>'},{'>','>','>','>','<','<','>'},{'>','>','>','>','>','<','>'},{'<','<','<','<','<','<','='},{'>','>','>','>','>','0','>'}};
void main()
{
	int i,m,n;
	char h,e;
	char B[20];
	stack S;
    stack initstack();
    int stackempty(stack S);
    void push(stack S,char e);
    char pop(stack S);
    char gettop(stack S);
    int getyx(char e);
    S=initstack();
    printf("输入一个中缀表达式.\n");
    scanf("%s",&B);
	printf("其相应的逆波兰式为：  ");
    i=0;
	while(B[i]!='\0')
	{
		if(B[i]>='a'&&B[i]<='z')
		{
			printf("%c",B[i]);
		}
		else 
		{
			while(!stackempty(S))  
				 {
					 m=getyx(B[i]);
				     e=gettop(S);
				     n=getyx(e);
				     if(yxjz[n][m]!='>'&&yxjz[n][m]!='0')
					 {
						 push(S,B[i]);
						 break;
					 }
				     else
                     	 if(B[i]==')')
						 {
						 lab:e=gettop(S);
							 if(e=='(')  {h=pop(S);break;}
							 else 
								 if(stackempty(S))
								 {
									 printf("wrong!\n");
									 return;
								 }
                                 else 
								 {
									 h=pop(S);
									 printf("%c",h);
									 goto lab;
								 }
						 }
						 else
						 {
							 h=pop(S);
							 printf("%c",h);
						 }
				 }
                 if(stackempty(S)) push(S,B[i]);
		}
				 i++;
	}
    while(!stackempty(S))
	{
		h=pop(S);
			printf("%c",h);
	}
	printf("\n");
}
stack initstack()
{
	stack m;
	m=malloc(sizeof(node));
	m->next=NULL;
	return(m);
}
int stackempty(stack S)
{
	if(S->next==NULL)
		return(1);
	else return(0);
}
void push(stack S,char e)
{
	stack a;
	a=malloc(sizeof(node));
    a->next=S->next;
	S->next=a;
    a->data=e;
}
char pop(stack S)
{
	stack a;
	char b;
	a=S->next;
	b=a->data;
	S->next=a->next;
	free(a);
	return (b);
	return('0');
}
char gettop(stack S)
{
	char e;
	e=S->next->data;
	return e;
}
int getyx(char e)
{ 
	int i,a;
	for(i=0;i<7;i++)
	{
		if(A[i]==e)
		{
			a=i;
			break;
		}
	}
    return a;
}