C语言中栈和队列实现表达式求值的实例

#include<stdio.h> #include<stdlib.h>  #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20  typedef int Status;  typedef char StackElemtype; typedef struct Stack{   StackElemtype* base;   StackElemtype* top;   int stackSize; }Stack; Status StackInit(Stack* s){   s->base = (StackElemtype*)malloc(sizeof(StackElemtype) * STACK_SIZE);   if( !s->base )     return ERROR;   s->top = s->base;   s->stackSize = STACK_SIZE;   return OK; } Status Pop(Stack* s,StackElemtype* value){   if( s->base == s->top ){     printf("/nstack empty/n");     return ERROR;   }   *value = *(--(s->top));   return OK; } Status Push(Stack* s,StackElemtype value){   if( s->top - s->base == s->stackSize){          s->base = (StackElemtype*)realloc(s->base,sizeof(StackElemtype) * (STACK_INCREMENT + STACK_SIZE));     if( !s->base )       return ERROR;     s->top = s->base + STACK_SIZE;     s->stackSize = STACK_SIZE + STACK_INCREMENT;   }   *(s->top) = value;   s->top++;   return OK; } int StackLength(Stack s){   return s.top - s.base; }  typedef double StackElemtype_ForValueExperssion; typedef struct Stack_2{   StackElemtype_ForValueExperssion* base;   StackElemtype_ForValueExperssion* top;   int stackSize; }Stack_2; Status StackInit_2(Stack_2* s){   s->base = (StackElemtype_ForValueExperssion*)malloc(sizeof(StackElemtype_ForValueExperssion) * STACK_SIZE);   if( !s->base )     return ERROR;   s->top = s->base;   s->stackSize = STACK_SIZE;   return OK; } Status Pop_2(Stack_2* s,StackElemtype_ForValueExperssion* value){   if( s->base == s->top ){     printf("/nstack empty/n");     return ERROR;   }   *value = *(--(s->top));   return OK; } Status Push_2(Stack_2* s,StackElemtype_ForValueExperssion value){   if( s->top - s->base == s->stackSize){     s->base = (StackElemtype_ForValueExperssion*)realloc(s->base,sizeof(StackElemtype_ForValueExperssion) * (STACK_INCREMENT + STACK_SIZE));     if( !s->base )       return ERROR;     s->top = s->base + STACK_SIZE;     s->stackSize = STACK_SIZE + STACK_INCREMENT;   }   *(s->top) = value;   s->top++;   return OK; }  typedef double QueueElemtype; typedef char  QueueOperatorValue; typedef struct QueueNode{   QueueElemtype data;   QueueOperatorValue operator;   struct QueueNode* next;   int flag; }QueueNode,*QueueNodePtr; typedef struct Queue{   QueueNodePtr front;   QueueNodePtr rear; }Queue;  Status QueueInit(Queue* q){   q->front = (QueueNodePtr)malloc(sizeof(QueueNode));   if( !q->front )     return ERROR;   q->rear = q->front;   q->rear->next = NULL;   return OK; } Status QueueInsert(Queue* q,QueueElemtype value){   QueueNodePtr new;   new = (QueueNodePtr)malloc(sizeof(QueueNode));   if( !new )     return ERROR;   new->data = value;   new->flag = 1;   new->next = NULL;   q->rear->next = new;   q->rear = new;   return OK; } Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value){   QueueNodePtr new;   new = (QueueNodePtr)malloc(sizeof(QueueNode));   if( !new )     return ERROR;   new->operator = value;   new->flag = 0;   new->next = NULL;   q->rear->next = new;   q->rear = new;   return OK; } Status QueueDelete(Queue* q,QueueElemtype* value,QueueOperatorValue *operator,int* symbol){   QueueNodePtr first;   if( q->front == q->rear )     return ERROR;   first = q->front->next;   if( first->flag == 1 ){     *value = first->data;     *symbol = 1;   }   else{     *operator = first->operator;     *symbol = 0;   }   q->front->next = first->next;   if( first == q->rear ){     q->rear = q->front;   }   return OK; }  /* 利用栈将中缀表达式转化为后缀表达式：  * ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――  * | 用户的输入  |      进行的处理      |  * |  0~9：   | 直接输出到控制台        |  * |  /，*，(  | 直接Push          |  * |  +，-    | 将栈中的元素Pop直到1.栈空或者是2.遇到(   |  * |  )     | 在遇到(之前将栈中的元素全部Pop   |  * ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――  * */  Status Infix2Postfix(Queue* q){   //Queue q;   //QueueInit(&q);   Stack s;   StackInit(&s);   char c,e;   char bufferDigit[10];   int i = 0;   double longDigit;   printf("    Please Enter Infix Expression/n");   printf("------------NOTE: end of '#'--------------/n");   scanf("%c", &c);   while( '#' != c){     while( c <= '9' && c >= '0' || '.' == c ){       bufferDigit[i++] = c;       bufferDigit[i] = '/0';       scanf("%c", &c);       if(!((c <= '9' && c >= '0' ) || '.' == c )){         longDigit = atof(bufferDigit);         QueueInsert(q,longDigit);         i = 0;       }     }     if( '(' == c || '*' == c || '/' == c ){       Push(&s, c);     }     else if( '+' == c || '-' == c ){       if( !StackLength(s) )         Push(&s, c);       else{         Pop(&s, &e);         while( '(' != e ){           QueueInsert_operatorValue(q, e);           if( StackLength(s) == 0 ){             break;           }else             Pop(&s, &e);         }         if( '(' == e )           Push(&s, e);         Push(&s, c);       }     }else if( ')' == c ){       Pop(&s, &e);       while( '(' != e ){         QueueInsert_operatorValue(q, e);         Pop(&s, &e);       }     }else if( '#' == c){       break;     }else{       printf("input ERROR!/n");       return ERROR;     }     scanf("%c", &c);   }   while(StackLength(s)){     Pop(&s, &e);     QueueInsert_operatorValue(q, e);   }   QueueInsert_operatorValue(q,'#');   return OK; } Status ShowQueue(Queue q){   printf("The Reverse Polish Notation is:");   if(q.front == q.rear){     printf("Queue Empty");     return ERROR;   }   QueueNodePtr p = q.front->next;   while(p != q.rear){     if(p->flag)       printf("%g ", p->data);     else       printf("%c ", p->operator);     p = p->next;    }   printf("/n");   return OK; }  /* 利用栈求解后缀表达式(逆波兰表达式)的值。  * ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――  * |  +，-，*，/，  |   将栈顶的两个元素弹出进行计算，将结果压入栈顶 |  * | 数字      |   将其压入栈顶                 |  * ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――  * */ Status ValueExpression(Queue q){   Stack_2 s;   StackInit_2(&s);   double o1;   double o2;   QueueElemtype number;   QueueOperatorValue operator;   int symbol;   QueueDelete(&q,&number,&operator,&symbol);   while( symbol == 1 || ( symbol == 0 && '#' != operator)){     if(symbol == 1){       Push_2(&s, number);     }     else if(symbol == 0){       switch(operator){         case '+':           Pop_2(&s,&o1);           Pop_2(&s,&o2);           Push_2(&s,o2 + o1);           break;         case '-':           Pop_2(&s,&o1);           Pop_2(&s,&o2);           Push_2(&s,o2 - o1);           break;         case '*':           Pop_2(&s,&o1);           Pop_2(&s,&o2);           Push_2(&s,o2 * o1);           break;         case '/':           Pop_2(&s,&o1);           Pop_2(&s,&o2);           Push_2(&s,o2 / o1);           break;       }     }     QueueDelete(&q,&number,&operator,&symbol);   }   Pop_2(&s,&o1);   printf("The Value of the Expression is %g/n",o1);   return OK; }  int main(){   Queue q;   QueueInit(&q);   Infix2Postfix(&q);   ShowQueue(q); /*   QueueElemtype number;   QueueOperatorValue operator;   int symbol;   QueueDelete(&q,&number,&operator,&symbol);   printf("%f,%c,%d/n",number,operator,symbol); */   ValueExpression(q); //Stack /*   Stack s;   StackInit(&s);   StackElemtype c;   Push(&s,'1');   Push(&s,'2');   Push(&s,'3');   Push(&s,'4');   Pop(&s,&c);   printf("%c ", c);   Pop(&s,&c);   printf("%c ", c);   Pop(&s,&c);   printf("%c ", c);   Pop(&s,&c);   printf("%c ", c); */   //Queue /*   Queue q;   QueueElemtype c;   QueueInit(&q);   QueueInsert(&q,1);   QueueInsert(&q,2);   QueueInsert(&q,3);   QueueInsert(&q,4);   QueueDelete(&q,&c);   printf("%d ", c);   QueueDelete(&q,&c);   printf("%d ", c);   QueueDelete(&q,&c);   printf("%d ", c);   QueueDelete(&q,&c);   printf("%d ", c);   if(QueueDelete(&q,&c)){     printf("%d ",c);   } */ /*   Queue q;   QueueInit(&q);   QueueInsert(&q,2.1);   QueueInsert_operatorValue(&q,'+');   QueueInsert(&q,43.1);   QueueInsert_operatorValue(&q,'a');   QueueInsert_operatorValue(&q,'(');   int iswho;   double d;   char c;   QueueDelete(&q,&d,&c,&iswho);   if(iswho == 1)     printf("%f ",d);   else     printf("%c ", c);   QueueDelete(&q,&d,&c,&iswho);   if(iswho == 1)     printf("%f ",d);   else     printf("%c ", c);   QueueDelete(&q,&d,&c,&iswho);   if(iswho == 1)     printf("%f ",d);   else     printf("%c ", c);   QueueDelete(&q,&d,&c,&iswho);   if(iswho == 1)     printf("%f ",d);   else     printf("%c ", c); */   return 0; }