当前位置： 首页 > news >正文

中缀、后缀表达式之间的相互转换 (配图解）

news 2026/6/13 16:26:07

目录

一、基本概念

1. 中缀表达式

2. 后缀表达式

二、算法转换思想

1.中缀转后缀表达式

2.后缀转中缀表达式

三、转换实现

1.中缀转后缀表达式实现

代码实现

图解详情

2.后缀转中缀表达式实现

代码实现

图解详情

四、整体实现过程

1.中缀转后缀表达式

2.后缀转中缀表达式

一、基本概念

1. 中缀表达式

基本概念

运算符放在两个操作数中间，这是我们常用的数学表达式，有括号和优先级。

例：a+b、5∗(3−2)、10+20/5

特点：依靠括号、运算符优先级、结合性决定计算顺序。

2. 后缀表达式

运算符放在两个操作数后面，这是为了访问计算机栈的运算，无括号、无优先级。

例： a+b（中缀） → ab+（后缀），5∗(3−2) → 5 3 2 −∗ 。

二、算法转换思想

1.中缀转后缀表达式

利用栈（Stack）数据结构来临时存储运算符。从左向右扫描中缀表达式，遇到操作数直接输出，遇到运算符则根其据优先级和栈顶元素进行比较，确保高优先级或相同优先级的左结合运算符先输出。

特殊情况： 遇到左括号时一直进栈至遇到右括号，然后将栈顶元素依次输出到左括号（注：左括号出栈不输出）。后面会有图解进行解析。

2.后缀转中缀表达式

从左向右扫描中缀表达式，遇到操作数压入栈中。遇到运算符：连续弹出栈顶两个片段（先弹的是右操作数，后弹的是左操作数），拼接格式：(左操作数 运算符 右操作数），运算后的结果重新压栈。重复以上操作。后面会配有图解进行解析。

三、转换实现

1.中缀转后缀表达式实现

代码实现

//利用枚举来表示字符 typedef enum { LEFT_PARE, RIGHT_PARE, ADD, SUB, MUL, DIV, MOD, EOS, NUM }contentType; char expr[] = "x/(i-j)*y"; //获取字符 contentType Get_token(char* symbol, int* index); //打印表达式 int Printf_token(ElemType token); //中缀转后缀表达式实现 int Proxfix(Stack* s) { //记录操作数 char symbol; //优先级 int in_stack[] = {0,19,12,12,13,13,13,0}; int out_stack[] = { 20,19,12,12,13,13,13,0 }; //记录下标 int index = 0; s->top = 0; //先在栈中放一个优先级最低的运算符 s->data[0] = EOS; contentType token; //huo token = Get_token(&symbol, &index); ElemType e; while (token != EOS) { //为操作数直接打印 if (token == NUM) { printf("%c", symbol); } //遇到右括号，依次出栈到左括号（左括号出栈不输出） else if(token == RIGHT_PARE) { while (s->data[s->top] != LEFT_PARE) { //出栈 Pop(s, &e); //出栈后不能直接输出，因为压入栈中的是枚举下标。 Printf_token(e); } //左括号不输出，直接出栈 Pop(s, &e); } //运算符进展 else { //让contentType中的枚举的索引做为下标 while (in_stack[s->data[s->top]] >= out_stack[token]) { Pop(s, &e); Printf_token(e); } Push(s, token); } //继续往下读取 token = Get_token(&symbol, &index); } //遇到“\0”将栈中的元素依次输出 Pop(s, &e); token = e; while (token != EOS) { Printf_token(e); Pop(s, &e); token = e; } printf("\n"); return 1; } //获取字符 contentType Get_token(char* symbol, int* index) { //让目标字符换，赋值给symbol *symbol = expr[*index]; //下一次获取下一个字符 *index = *index + 1; //开始判断 switch (*symbol) { case'(': return LEFT_PARE; case')': return RIGHT_PARE; case'+': return ADD; case'-': return SUB; case'*': return MUL; case'/': return DIV; case'%': return MOD; case'\0': return EOS; default: return NUM; } } //打印表达式 int Printf_token(ElemType token) { switch (token) { case LEFT_PARE: printf("("); break; case RIGHT_PARE: printf(")"); break; case ADD: printf("+"); break; case SUB: printf("-"); break; case MUL: printf("*"); break; case DIV: printf("/"); break; case MOD: printf("%%"); break; default: return 0; } return 1; }

图解详情

2.后缀转中缀表达式实现

代码实现

//用枚举表示字符 typedef enum { LEFT_PARE, RIGHT_PARE, ADD, SUB, MUL, DIV, MOD, EOS, NUM }contentType; //内容 char expr[] = "82/2+56*-"; //获取字符 contentType Get_token(char* symbol, int* index); //后缀表达式转中缀表达式 int Eval(Stack*s) { char symbol; int op1, op2; int index = 0; contentType token; token = Get_token(&symbol, &index); ElemType result; while (token != EOS) { if (token == NUM) { Push(s, symbol - '0'); } else { Pop(s, &op2); Pop(s, &op1); } switch(token) { case ADD: Push(s, op1 + op2); break; case SUB: Push(s, op1 - op2); break; case MUL: Push(s, op1 * op2); break; case DIV: Push(s, op1 / op2); break; case MOD: Push(s, op1 % op2); break; default: break; } token = Get_token(&symbol, &index); } Pop(s, &result); printf("%d\n", result); return 1; } //获取字符 contentType Get_token(char* symbol, int* index) { *symbol = expr[*index]; *index = *index + 1; switch (*symbol) { case'(': return LEFT_PARE; case')': return RIGHT_PARE; case'+': return ADD; case'-': return SUB; case'*': return MUL; case'/': return DIV; case'%': return MOD; case'\0': return EOS; default: return NUM; } }

图解详情

四、整体实现过程

1.中缀转后缀表达式

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> //定义顺序表 #define MAXSIZE 100 typedef int ElemType; typedef struct { ElemType *data; int top;//栈顶指针 }Stack; typedef enum { LEFT_PARE, RIGHT_PARE, ADD, SUB, MUL, DIV, MOD, EOS, NUM }contentType; //初始化 Stack* InitStack() { Stack* s = (Stack*)malloc(sizeof(Stack)); if (s == NULL) { perror("InitStack:s"); return NULL; } s->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); s->top = -1; return s; } //判断是否为空 int IsEmpt(Stack* s) { if (s->top == -1) { printf("空的\n"); return 1; } else { return 0; } } //入栈 int Push(Stack* s, ElemType e) { if (s->top >= MAXSIZE - 1) { printf("空栈\n"); return 0; } s->top++; s->data[s->top] = e; return 1; } //出栈 int Pop(Stack* s, ElemType* e) { if (s->top == -1) { printf("空的\n"); return 0; } *e = s->data[s->top]; s->top--; return 1; } //获取栈顶元素 int GetTop(Stack* s, ElemType* e) { if (s->top == -1) { printf("空的\n"); return 0; } *e = s->data[s->top]; return 1; } char expr[] = "x/(i-j)*y"; //获取字符 contentType Get_token(char* symbol, int* index); ////打印表达式 int Printf_token(ElemType token); //中缀转后缀表达式实现 int Proxfix(Stack* s) { //记录操作数 char symbol; //优先级 int in_stack[] = {0,19,12,12,13,13,13,0}; int out_stack[] = { 20,19,12,12,13,13,13,0 }; //记录下标 int index = 0; s->top = 0; //先在栈中放一个优先级最低的运算符 s->data[0] = EOS; contentType token; //huo token = Get_token(&symbol, &index); ElemType e; while (token != EOS) { //为操作数直接打印 if (token == NUM) { printf("%c", symbol); } //遇到右括号，依次出栈到左括号（左括号出栈不输出） else if(token == RIGHT_PARE) { while (s->data[s->top] != LEFT_PARE) { //出栈 Pop(s, &e); //出栈后不能直接输出，因为压入栈中的是枚举下标。 Printf_token(e); } //左括号不输出，直接出栈 Pop(s, &e); } //运算符进展 else { //让contentType中的枚举的索引做为下标 while (in_stack[s->data[s->top]] >= out_stack[token]) { Pop(s, &e); Printf_token(e); } Push(s, token); } //继续往下读取 token = Get_token(&symbol, &index); } //遇到“\0”将栈中的元素依次输出 Pop(s, &e); token = e; while (token != EOS) { Printf_token(e); Pop(s, &e); token = e; } printf("\n"); return 1; } //获取字符 contentType Get_token(char* symbol, int* index) { //让目标字符换，赋值给symbol *symbol = expr[*index]; //下一次获取下一个字符 *index = *index + 1; //开始判断 switch (*symbol) { case'(': return LEFT_PARE; case')': return RIGHT_PARE; case'+': return ADD; case'-': return SUB; case'*': return MUL; case'/': return DIV; case'%': return MOD; case'\0': return EOS; default: return NUM; } } ////打印表达式 int Printf_token(ElemType token) { switch (token) { case LEFT_PARE: printf("("); break; case RIGHT_PARE: printf(")"); break; case ADD: printf("+"); break; case SUB: printf("-"); break; case MUL: printf("*"); break; case DIV: printf("/"); break; case MOD: printf("%%"); break; default: return 0; } return 1; } int main() { //初始化 Stack* s = InitStack(); //中缀表达式 printf("%s\n", expr); //转后缀表达式后的结果 Proxfix(s); return 0; }

2.后缀转中缀表达式

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef int ElemType; typedef struct stack { ElemType data; struct stack* next; }Stack; //用枚举表示字符 typedef enum { LEFT_PARE, RIGHT_PARE, ADD, SUB, MUL, DIV, MOD, EOS, NUM }contentType; char expr[] = "82/2+56*-"; //初始化 Stack* InitStack() { Stack* s = (Stack*)malloc(sizeof(Stack)); if (s == NULL) { perror("InitStack:s"); return NULL; } s->data = 0; s->next = NULL; return s; } //判断是否为空 int IsEmpty(Stack* s) { if (s->next == NULL) { printf("空栈\n"); return 1; } else { return 0; } } //入栈 int Push(Stack* s, ElemType e) { assert(s); //开辟空间 Stack* p = (Stack*)malloc(sizeof(Stack)); if (p == NULL) { perror("Push:p"); return 0; } p->data = e; p->next = s->next; s->next = p; return 1; } //出栈 int Pop(Stack* s, ElemType* e) { if (s->next == NULL) { printf("空栈\n"); return 0; } *e = s->next->data; Stack* q = s->next; s->next = q->next; free(q); q = NULL; return 1; } //获取字符 contentType Get_token(char* symbol, int* index); //后缀表达式转中缀表达式 int Eval(Stack*s) { char symbol; int op1, op2; int index = 0; contentType token; token = Get_token(&symbol, &index); ElemType result; while (token != EOS) { if (token == NUM) { Push(s, symbol - '0'); } else { Pop(s, &op2); Pop(s, &op1); } switch(token) { case ADD: Push(s, op1 + op2); break; case SUB: Push(s, op1 - op2); break; case MUL: Push(s, op1 * op2); break; case DIV: Push(s, op1 / op2); break; case MOD: Push(s, op1 % op2); break; default: break; } token = Get_token(&symbol, &index); } Pop(s, &result); printf("%d\n", result); return 1; } //获取字符 contentType Get_token(char* symbol, int* index) { *symbol = expr[*index]; *index = *index + 1; switch (*symbol) { case'(': return LEFT_PARE; case')': return RIGHT_PARE; case'+': return ADD; case'-': return SUB; case'*': return MUL; case'/': return DIV; case'%': return MOD; case'\0': return EOS; default: return NUM; } } //获取队头元素 int GetPop(Stack* s,ElemType*e) { if (s->next == NULL) { printf("为空\n"); return 0; } *e = s->next->data; return 1; } //调用 int main() { Stack* s = InitStack(); Eval(s); return 0; }
http://www.gsyq.cn/news/1496377.html

相关文章：

  • Paperxie 工科攻坚利器：AI 代码生成一键搞定毕业论文程序源码难题
  • 基于Keras的垃圾分类图像识别实战包（含训练模型、50张实拍测试图与完整设计报告）
  • SpringData JPA也能写sql，为什么还要用mybatis?
  • linux下安装gitlab
  • 番禺洛浦奢侈品回收第一名｜金小福名表名包名酒钻石翡翠黄金全品类专业回收 - 花生花生1
  • 2026年AI问答流量服务公司选购指南：技术架构、行业应用与决策框架 - 优质品牌商家
  • 2026 主流 GEO 源码厂商实测：云罗 GEO、摘星智能、棋引科技技术与落地能力对比
  • BiliBili-UWP桌面版终极秘籍：告别卡顿，打造你的专属B站体验
  • idea+git插件+云备份实现项目新分支新建维护
  • 前端周刊2026W22 | React 13周年、TanStack Router、Deno 2.8、Node.js 26、npm 分阶段发布
  • 防割面料采购怎么避坑，选UHMWPE梭织面料供应商为什么更稳
  • Android 权限请求构建器使用指南
  • 粗心和专注力有关系吗？
  • 七界梦谭长戟刚鬣怎么打 七界梦谭长戟刚鬣详细打法攻略
  • QQ本地缓存机制初步探寻
  • 2026年免费AI编程工具推荐榜单
  • Unity基础（十四）场景异步加载
  • OpenSpec实战
  • android开发 原生设置中的Device name 与Device model
  • 学习比特 享幸福人生
  • 2026高考大数据：1290万考生背后的赛道拥挤度与捡漏指南
  • GEO基础优化包含哪些基础项目
  • Redis中的通用命令
  • 论文去重难？5个实用工具帮你
  • Boss-Key：终极窗口隐私保护神器，一键隐藏桌面窗口的完整指南
  • 2026河马引力67W避坑：分配不均协议阉割散热差别买
  • Java 文件复制（字符 / 字节缓冲流）
  • 人形机器人进真实场景，开发者需要关注哪些技术栈？
  • 创建订单报错‘无定价过程被确定’
  • 水性机调色浆WM系列技术优势：纳米分散赋能高效调色