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

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;
}

以上就是C语言数据结构中栈和队列的应用，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/robin_xu_shuai/article/details/50859455