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

—-想了解C语言中栈和队列实现表达式求值的实例分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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 emptyn");       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 emptyn");       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 Expressionn");     printf("------------NOTE: end of '#'--------------n");     scanf("%c", &c);     while( '#' != c){       while( c <= '9' && c >= '0' || '.' == c ){         bufferDigit[i++] = c;         bufferDigit[i] = '';         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 %gn",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,%dn",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;   }     

• 1
• 2
• 下一页