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语言数据结构中栈和队列的应用，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C语言中栈和队列实现表达式求值  # 表达式求值的实现  # C语言 浅谈栈与队列的定义与操作  # C语言数据结构进阶之栈和队列的实现  # C语言编程数据结构栈与队列的全面讲解示例教程  # C语言编程数据结构的栈和队列  # C语言用栈和队列实现的回文检测功能示例  # C语言 表、栈和队列详解及实例代码  # 深入浅析C语言中堆栈和队列  # C语言超详细讲解栈与队列实现实例  # 波兰  # 如有  # 将其  # 数据结构  # 希望能  # 弹出  # 或者是  # 谢谢大家  # 转化为  # 前将  # 疑问请  # 求值  # Pop  # base  # printf  # top  # malloc  # StackInit  # stackSize  # return 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 微信小程序 require机制详解及实例代码  百度输入法全感官ai怎么关 百度输入法全感官皮肤关闭  javascript中对象的定义、使用以及对象和原型链操作小结  东莞专业网站制作公司有哪些,东莞招聘网站哪个好？  Laravel路由Route怎么设置_Laravel基础路由定义与参数传递规则【详解】  HTML透明颜色代码怎么让图片透明_给img元素加透明色的技巧【方法】  Laravel如何生成API文档？（Swagger/OpenAPI教程）  Laravel如何构建RESTful API_Laravel标准化API接口开发指南  1688铺货到淘宝怎么操作 1688一键铺货到自己店铺详细步骤  猎豹浏览器开发者工具怎么打开 猎豹浏览器F12调试工具使用【前端必备】  VIVO手机上del键无效OnKeyListener不响应的原因及解决方法  Laravel怎么返回JSON格式数据_Laravel API资源Response响应格式化【技巧】  EditPlus中的正则表达式实战(5)  浅述节点的创建及常见功能的实现  如何用狗爹虚拟主机快速搭建网站？  佐糖AI抠图怎样调整抠图精度_佐糖AI精度调整与放大细化操作【攻略】  Laravel的辅助函数有哪些_Laravel常用Helpers函数提高开发效率  Laravel Eloquent性能优化技巧_Laravel N+1查询问题解决  利用vue写todolist单页应用  如何用腾讯建站主机快速创建免费网站？  mc皮肤壁纸制作器,苹果平板怎么设置自己想要的壁纸我的世界？  Python文本处理实践_日志清洗解析【指导】  图册素材网站设计制作软件,图册的导出方式有几种？  高端智能建站公司优选：品牌定制与SEO优化一站式服务  Laravel表单请求验证类怎么用_Laravel Form Request分离验证逻辑教程  Android中AutoCompleteTextView自动提示  Laravel如何使用Blade组件和插槽？（Component代码示例）  小米17系列还有一款新机？主打6.9英寸大直屏和旗舰级影像  Laravel怎么配置不同环境的数据库_Laravel本地测试与生产环境动态切换【方法】  Laravel如何自定义错误页面（404, 500）？（代码示例）  高防服务器：AI智能防御DDoS攻击与数据安全保障  如何用花生壳三步快速搭建专属网站？  Laravel如何理解并使用服务容器（Service Container）_Laravel依赖注入与容器绑定说明  Laravel中DTO是什么概念_在Laravel项目中使用数据传输对象(DTO)  高端建站三要素：定制模板、企业官网与响应式设计优化  php读取心率传感器数据怎么弄_php获取max30100的心率值【指南】  轻松掌握MySQL函数中的last_insert_id()  HTML透明颜色代码怎么让下拉菜单透明_下拉菜单透明背景指南【技巧】  Laravel如何集成第三方登录_Laravel Socialite实现微信QQ微博登录  公司门户网站制作公司有哪些,怎样使用wordpress制作一个企业网站？  北京企业网站设计制作公司,北京铁路集团官方网站？  laravel怎么使用数据库工厂（Factory）生成带有关联模型的数据_laravel Factory生成关联数据方法  Laravel如何实现API速率限制？（Rate Limiting教程）  如何在阿里云部署织梦网站？  如何生成腾讯云建站专用兑换码？  购物网站制作费用多少,开办网上购物网站，需要办理哪些手续？  ,南京靠谱的征婚网站？  Android Socket接口实现即时通讯实例代码  公司网站制作需要多少钱,找人做公司网站需要多少钱？  如何为不同团队 ID 动态生成多个“认领值班”按钮