nibolan.cpp

数据结构课程设计

//#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<iostream>

using namespace std;

typedef struct Node
{
	char data;
	struct Node  *next;
}LinkQueueNode;


typedef struct
{
	LinkQueueNode *front;
	LinkQueueNode *rear;
}LinkQueue;


int InitQueue(LinkQueue *Q) 
{  Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(Q->front!=NULL)
	{
		Q->rear=Q->front;
		Q->front->next=NULL;
		return 1;
	}

	else  return 0;
}


int EnterQueue(LinkQueue *Q,int x)
{
	LinkQueueNode *NewNode;
    NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(NewNode!=NULL)
	{
		NewNode->data=x;
		NewNode->next=NULL;
		Q->rear->next=NewNode;
		Q->rear=NewNode;
		return 1;
	}
	else  return 0;
}



int DeleteQueue(LinkQueue *Q,int *x)
{
	LinkQueueNode *p;
	if(Q->front==Q->rear)
	   return 0;
	p=Q->front->next;
	Q->front->next=p->next;
	if(Q->rear==p)
	  Q->rear=Q->front;
	*x=p->data;
	free(p);
	return 1;
}


//C++ 重载机制





typedef struct 
{
	char elem[20];
	int top;
}SeqStack;




int Push( SeqStack  *S,char x) 
{ 

	if(S->top==20-1)
		return 0; 
    else 
	{
	S->top++;
	S->elem[S->top]=x;
	}
    return 1 ;
}
//********************************
int Push( SeqStack  *S,int x) 
{ 

	if(S->top==20-1)
		return 0; 
    else 
	{
	S->top++;
	S->elem[S->top]=x;
	}
    return 1 ;
}
//********************************
void InitStack(SeqStack *S)
{
	S->top=-1;
};



int Pop( SeqStack *S,char *x)
{
	 if(S->top==-1)
		 return 0;
	 else
	 {
		 *x=S->elem[S->top];
		 S->top--;
		 return 1;
		
	 }
}


int Pop( SeqStack *S,int *x)
{
	 if(S->top==-1)
		 return 0;
	 else
	 {
		 *x=S->elem[S->top];
		 S->top--;
		 return 1;
		
	 }
}
//**************************
char GetTop(SeqStack *S) 
{
	
	if(S->top==-1)
		return 0; 
	else
	{
	  return S->elem[S->top];
	}
}

char Compare(char str,char ch)
{   
	
	char a[8][8] ={ { ' ' , '+' , '-' , '*' , '/' , '(' , ')' , '#' },
			{ '+' , '>' , '>' , '<' , '<' , '<' , '>' , '>' },
			{ '-' , '>' , '>' , '<' , '<' , '<' , '>' , '>' },
			{ '*' , '>' , '>' , '>' , '>' , '<' , '>' , '>' },
			{ '/' , '>' , '>' , '>' , '>' , '<' , '>' , '>' },
			{ '(' , '<' , '<' , '<' , '<' , '<' , '=' , ' ' },
			{ ')' , '>' , '>' , '>' , '>' , ' ' , '>' , '>' },
			{ '#' , '<' , '<' , '<' , '<' , '<' , ' ' , '=' }, };
	int i ;
	int j ;  
	for(i=0;i<8;i++)
	{
		if(a[i][0]==str)
		{
			for(j=0;j<8;j++)
			    if(a[0][j]==ch)
				   return(a[i][j]);
		}
	}
}



int Execute( int a, char op, int b)
{
	switch(op)
	{	
	case'+':
		     return a+b;
			 break;
	case'-':
		     return a-b;
		     break;
	case'*':
		     return a*b;
			 break;
	case'/':
		     return a/b;
			 break;
	}
}




















void ExchangeEvaluation()//SeqStack & YSS,char & st[])
{
    int k=1;
	char st[10];
	LinkQueue OVS;
	InitQueue(&OVS);
	SeqStack OPTR;
	InitStack(&OPTR);
	char ch;
	Push(&OPTR,'#');
	printf("\n请输入一个表达式串\n");
	ch=getchar();
	while(ch!='#'||GetTop(&OPTR)!='#')
		
	{
		char op;
		/*****************************************************************
		if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&ch!='('&&ch!=')'&&ch!='#')
		//if(ch<='z'&&ch>='a')
		{  // printf("*******************\n";
		     EnterQueue(&OVS,ch);
             ch=getchar();
		//	printf(" %c--",ch);
		}

     //    ***********************************************************************/
       if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&ch!='('&&ch!=')'&&ch!='#')
		{   
     		int temp;
	    	temp=ch-'0';
        
    		ch=getchar();
           
    		while(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&ch!='('&&ch!=')'&&ch!= '#')
			{
     			temp=temp*10+ch-'0';
            
    			ch=getchar();
		
			}
        	EnterQueue(&OVS,temp);
			

		}
	
		else
		{   
			switch(Compare(GetTop(&OPTR),ch))
			{
			case '<':
				      Push(&OPTR,ch);
					 ch=getchar();break;
		              
			case '=':
					 Pop(&OPTR,&op);
					 ch=getchar();break;

			case '>':
				     Pop(&OPTR,&op);
					 st[k++]=op;
					// EnterQueue(&OVS,op);
			
					 break;
			}
		}
	}
     



     SeqStack YSS;
	InitStack(&YSS);

	while(OVS.front->next!=NULL)  //或者while(Q->front!=Q->rear)
	  {
		  int x;DeleteQueue(&OVS,&x);
		  printf("%d   ",x);
		  //在创建一个栈 将运算数 压入
		  Push(&YSS,x);

	  }
/*    while(OPTR.top!=-1)  //或者while(Q->front!=Q->rear)
	  {
		  char y;Pop(&OPTR,&y);
		  printf("%c   ",y);
	  }
	  printf("\n");
*/
	for(int i=1;i<k;i++)
		printf("%c   ",st[i]);


   //根据后缀表达式求值
	printf("\n根据后缀表达式求值:\n");
	int num1,num2,num3;
	int j=0;
    while(YSS.top!=0)
	{
		Pop(&YSS,&num1);
		Pop(&YSS,&num2);
        num3=Execute( num1,st[j++], num2);
      Push(&YSS, num3);
	}

     int sum;
     Pop(&YSS,&sum);
     printf("\n输出运算结果sum=%d",sum);
}




				    

void main()
{     
     // SeqStack Seq;
	 // InitStack(&Seq);
	 // char st[10];
	 ExchangeEvaluation();//Seq,st);
	 
}