szys.c

利用堆栈实现有理数的四则运算

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define NumberType double
#define NULL 0
#define DataType char
typedef struct Node *PNode;
typedef struct LinkList *PLinkList;
typedef struct LinkStack *PLinkStack;

struct Node
{
  DataType info;
  PNode link;
};
struct LinkStack
{ PNode base;
  PNode top;
};
struct LinkList
{ PNode base;
  PNode top;
};

PLinkList Create_LinkListPointer(void)
{PLinkList pllist;
 pllist=(PLinkList)malloc(sizeof(struct LinkList));
 if(pllist==NULL) pllist=(PLinkList)realloc(sizeof(struct LinkList));
 else pllist->top=pllist->base=NULL;
 return (pllist);
}

PLinkList Create_LinkList(PLinkList pllist)
{pllist->top=(PNode)malloc(sizeof(struct Node));
 if(pllist->top==NULL) pllist->top=(PNode)realloc(sizeof(struct Node));
 else {pllist->base=pllist->top;
  pllist->base->link=pllist->top->link=NULL;
 }
 return (pllist);
}

PLinkList Create_LinkListNode(PLinkList pllist)
{pllist->top->link=(PNode)malloc(sizeof(struct Node));
 if(pllist->top->link==NULL) pllist->top->link=(PNode)realloc(sizeof(struct Node));
 else{ pllist->top=pllist->top->link;
  pllist->top->link=NULL;
 }
 return(pllist);
}


PLinkStack Create_LinkStackPointer(void)
{PLinkStack plstack;
 plstack=(PLinkStack)malloc(sizeof(struct LinkStack));
 if(plstack==NULL) plstack=(PLinkStack)realloc(sizeof(struct LinkStack));
 else plstack->top=plstack->base=NULL;
 return (plstack);
}

PLinkStack Create_LinkStack(PLinkStack plstack)
{plstack->top=(PNode)malloc(sizeof(struct Node));
 if(plstack->top==NULL) plstack->top=(PNode)realloc(sizeof(struct Node));
 else {plstack->base=plstack->top;
  plstack->top->link=plstack->base->link=NULL;
 }
 return(plstack);
}

PLinkStack Create_LinkStackNode(PLinkStack plstack)
{plstack->top->link=(PNode)malloc(sizeof(struct Node));
 if(plstack->top->link==NULL) plstack->top->link=(PNode)malloc(sizeof(struct Node));
 else{plstack->top=plstack->top->link;
  plstack->top->link=NULL;
 }
 return(plstack);
}


PLinkStack push_stack(PLinkStack plstack,DataType i)
{plstack->top->link=(PNode)malloc(sizeof(struct Node));
 if(plstack->top->link==NULL) plstack->top->link=(PNode)realloc(sizeof(struct Node));
 else {plstack->top=plstack->top->link;
       plstack->top->link=NULL;
       plstack->top->info=i;
      }
 return (plstack);
}


PLinkStack pop_stack_all(PLinkList pllist,PLinkStack plstack)
{PNode p;
 while(plstack->top!=plstack->base){
  p=plstack->base;
  while(p->link!=plstack->top) p=p->link;
  Create_LinkListNode(pllist);
  pllist->top->info=plstack->top->info;
  plstack->top=plstack->top->link;
  plstack->top=p;
 }
 return (plstack);
}

PLinkList print_llist(PLinkList pllist)
{PNode temp;
 temp=pllist->base;
 while(temp!=pllist->top){
  printf("%c",temp->link->info);
  temp=temp->link;
 }
 printf("\n");
 return (pllist);
}

int bracket_included(PLinkStack plstack)
{PNode p,q;
 q=p=plstack->base;
 while(p!=plstack->top)
 {if( p->link->info=='(' || p->link->info==')') q=p->link;
  p=p->link;
 }
 if(q->info=='(' || q->info ==')') return (1);
 else return (0);
}

int islower_included(PLinkStack plstack)
{PNode p,q;
 q=p=plstack->base;
 while(p!=plstack->top){
  if(p->link->info=='+' || p->link->info=='-' ) q=p->link;
  p=p->link;
 }
 if(q!=plstack->base &&(q->info=='+' || q->info =='-')) return (1);
 else return (0);
}

int bracket_included_and_lower(PLinkStack plstack)
{PNode p,q;
 p=plstack->base ;
 while(p!=plstack->top){
  if(p->link->info==')' ) q=p->link;
  p=p->link;
 }
 p=q;
 while(p!=plstack->top){
  if(p->link->info=='+' || p->link->info=='-') q=p->link;
  p=p->link;
 }
 if(q->info=='+' || q->info=='-') return (1);
 else return (0);
}

PLinkList push_LinkList(PLinkList pllist,DataType i)
{
 Create_LinkListNode(pllist);
 pllist->top->info=i;
 return(pllist);
}

PLinkList push_underline(PLinkList pllist)
{Create_LinkListNode(pllist);
 pllist->top->info='_';
 return (pllist);
}

PLinkStack pop_stack_until_bracket(PLinkList pllist,PLinkStack plstack)
{PNode p,q;
 p=plstack->base;
 while(p!=plstack->top){
  if(p->link->info=='(') q=p->link;
  p=p->link;
 }
 p=q;
 while(plstack->top!=p){
  q=plstack->base;
  while(q->link!=plstack->top) q=q->link;
  Create_LinkListNode(pllist);
  pllist->top->info=plstack->top->info;
  plstack->top=plstack->top->link;
  plstack->top=q;
 }
 return (plstack);
}

PLinkStack pop_until_lower(PLinkList pllist,PLinkStack plstack)
{PNode p,q;
 p=plstack->base;
 while(p!=plstack->top){
  if(p->link->info=='+' || p->link->info=='-') q=p->link;
  p=p->link;
 }
 p=q;
 while(plstack->top!=p){
  q=plstack->base;
  while(q->link!=plstack->top) q=q->link;
  Create_LinkListNode(pllist);
  pllist->top->info=plstack->top->info;
  plstack->top=plstack->top->link;
  plstack->top=q;
 }
 return (plstack);
}
PLinkStack pop_stack_until_bracket_lower(PLinkList pllist,PLinkStack plstack)
{PNode p,q;
 p=plstack->base;
 while(p->info!='(') p=p->link;
 q=p;
 while(plstack->top!=q){
 p=q;
 while(q->link!=plstack->top) q=q->link;
 Create_LinkListNode(pllist);
 pllist->top->info=plstack->top->info;
 plstack->top=plstack->top->link;
 plstack->top=q;
 }
 return (plstack);
}

PLinkStack pop_one(PLinkStack plstack)
{PNode p;
 p=plstack->base;
 while(p->link!=plstack->top) p=p->link;
 plstack->top=plstack->top->link;
 plstack->top=p;
 return (plstack);
}

PLinkStack pop_all(PLinkList pllist,PLinkStack plstack)
{PNode p;
 if(!isOperator(pllist->top->info)&&pllist->top->info!='_') push_underline(pllist);
 while(plstack->top!=plstack->base){
  p=plstack->base;
  while(p->link!=plstack->top) p=p->link;
  Create_LinkListNode(pllist);
  pllist->top->info=plstack->top->info;
  plstack->top=plstack->top->link;
  plstack->top=p;
 }
 return (plstack);
}
int isOperator(DataType i)
{
  if(i=='+' || i=='-' || i=='*' || i=='/' || i=='(' || i==')') return (1);
  else return (0);
}

int isPoint_included(PNode p)
{
 PNode q,temp;
 q=p;
 while(q->link->info!='_'){
  if(q->info=='.') temp=q;
  q=q->link;
 }
 if(temp->info=='.') return (1);
 else return (0);
}

int Calculator_underline(PNode p)
{
 PNode q;
 int i;
 i=0;
 q=p;
 while(!isOperator(q->link->info)){
  if(q->link->info=='_') i++;
  q=q->link;
 }
 return (i);
}

NumberType Calculator(PLinkList pllist)
{
 PNode p,q,temp,temp1,swap;
    int i,j;
 NumberType t,t1,t2,tmark1,tmark2,m;
 t=t1=t2=0;
 q=p=pllist->base;
 while(!isOperator(p->link->info)) p=p->link;/* find p */
 while(p!=pllist->top){
  /**************************************************************/
  /**************************************************************/
  if(!isOperator(p->info)&&p->link==pllist->top){
    if(q==pllist->base){                     /* find q */
         while(q!=p){
         if(q->info=='_') temp=q;
         q=q->link;
      }
         q=temp;
   }
   temp1=temp=pllist->base;
      while(temp!=q){                         /* find temp */
         if(temp->info=='_') temp1=temp;
         temp=temp->link;
   }
      temp=temp1; temp1=pllist->base;
      /*////////// Calculate function /////////////////////*/
      swap=q; i=0;       /* calculate t1 */
   if(isPoint_included(q)){           /*include point */
    while(swap->link->info!='.'){swap=swap->link;i++;}
    swap=q;
    while(swap->link->info!='.'&&--i!=0){
     j=i;
     m=(NumberType)swap->link->info-'0';
     while(j--!=0) m=m*10;
     t1=t1+m;
     swap=swap->link;
    }
    if(i==0) {t1=t1+(NumberType)swap->link->info-'0'; swap=swap->link->link;}
    i=1;
    while(swap->link->info!='_'){
     j=i;
     m=(NumberType)swap->link->info-'0';
     while(j--!=0) m=m*1/10;
     t1=t1+m;
     swap=swap->link;
     i++;
    }
   }
   else if(!isPoint_included(q)){     /*doesn't include point*/
          while(swap->link->info!='_') {swap=swap->link; i++;}
          swap=q;
          while(swap->link->info!='_'&&--i!=0) {
      j=i;
      m=(NumberType)swap->link->info-'0';
      while(j--!=0) m=m*10;
             t1=t1+m;
            swap=swap->link;
    }
    if(i==0) {t1=t1+(NumberType)swap->link->info-'0';swap=swap->link;}
   }
      swap=temp; t2=0;i=0;   /* calculate t2 */
   if(isPoint_included(temp)){   /*include point */
    while(swap->link->info!='.'){swap=swap->link;i++;}
    swap=temp;
    while(swap->link->info!='.'&&--i!=0){
     j=i;
     m=(NumberType)swap->link->info-'0';
     while(j--!=0) m=m*10;
     t2=t2+m;
     swap=swap->link;
    }
    if(i==0||i==-1) {t2=t2+(NumberType)swap->link->info-'0'; swap=swap->link->link;}
    i=1;
    while(swap->link->info!='_'){
     j=i;
     m=(NumberType)(swap->link->info-'0');
     while(j--!=0) m=m*1/10;
     t2=t2+m;
     swap=swap->link;
     i++;
    }
   }
   else if(!isPoint_included(temp)){
    while(swap->link->info!='_'){swap=swap->link;i++;}
          swap=temp;
          while(swap->link->info!='_'&&--i!=0) {
      j=i;
      m=(NumberType)swap->link->info-'0';
      while(j--!=0) m=m*10;
        t2=t2+m;
            swap=swap->link;
    }
    if(i==0||i==-1) {t2=t2+(NumberType)swap->link->info-'0';swap=swap->link;}
   }
   if(p->link->info=='+') t=t1+t2;
   else if(p->link->info=='-') t=t2-t1;
   else if(p->link->info=='*') t=t1*t2;
   else if(p->link->info=='/') t=t2/t1;
      /*///// Deal with the left //////////////////*/
     q=temp;
     p=p->link;
  }
  /*******************************************************************/
  /*******************************************************************/
 else if(!isOperator(p->info)&&isOperator(p->link->link->info)){
      if(q==pllist->base){                     /* find q */
         while(q!=p){
         if(q->info=='_') temp=q;
         q=q->link;
      }
         q=temp;
   }
   temp1=temp=pllist->base;
      while(temp!=q){                         /* find temp */
         if(temp->info=='_') temp1=temp;
         temp=temp->link;
   }
      temp=temp1; temp1=pllist->base;
      /*////////// Calculate function /////////////////////*/
      swap=q; i=0;       /* calculate t1 */