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

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

news 2026/6/10 2:30:16

目录

一、基本概念

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.jsqmd.com/news/984637/

相关文章：

  • 计算机毕业设计之基于python的企业员工管理系统设计与实现
  • WebBuilder基础架构与模块文件运行机制详解
  • 文献阅读 260609-Releasing global forests from human management: How much more carbon could be stored
  • 重新定义物联网架构：物联大师的企业级边缘计算解决方案
  • 如何基于 AI Agent 构建推理调度平台
  • TQVaultAE终极指南：如何彻底解决《泰坦之旅》仓库空间不足的烦恼
  • 梧桐智算：专业级可研报告生成效果实测
  • linux下安装gitlab
  • 基于Keras的垃圾分类图像识别实战包（含训练模型、50张实拍测试图与完整设计报告）
  • SpringData JPA也能写sql，为什么还要用mybatis?
  • 物理层的FPGA实现的思考总结（1）
  • Paperxie 工科攻坚利器：AI 代码生成一键搞定毕业论文程序源码难题
  • 防眩光AG+硬化复合板厂家推荐：复合功能板适合哪些应用场景
  • 番禺洛浦奢侈品回收第一名｜金小福名表名包名酒钻石翡翠黄金全品类专业回收 - 花生花生1
  • PyMuPDF：这个 Python 库，把 PDF 所有操作都覆盖了
  • 苹果WWDC26引爆全端AI产品，Meta/WIMI微美全息加速抢滩XR眼镜硬件市场
  • BiliBili-UWP桌面版终极秘籍：告别卡顿，打造你的专属B站体验
  • 2026年AI问答流量服务公司选购指南：技术架构、行业应用与决策框架 - 优质品牌商家
  • LumeValley｜企业级Agent全栈开发，AI智能体规模化落地
  • 2026必看！独立开发者高性价比AI编程工具大全
  • Boss-Key：Windows用户的隐私守护神，一键隐藏窗口的终极解决方案
  • 2026 主流 GEO 源码厂商实测：云罗 GEO、摘星智能、棋引科技技术与落地能力对比
  • Effective C++ 条款06：若不想使用编译器自动生成的函数，就应该明确拒绝
  • 重新定义音乐自由：插件化播放器如何让你真正掌控音乐体验
  • 抗垢水路：SEGE在硬水地区保持清爽
  • idea+git插件+云备份实现项目新分支新建维护
  • 视觉伺服：基于图像的IBVS与基于位置的PBVS
  • 如何让《Honey Select 2》游戏体验全面升级：HS2-HF_Patch终极指南
  • Whisky终极指南：在macOS上轻松运行Windows程序的5个简单步骤
  • 3分钟搞定Windows和Office激活：KMS_VL_ALL_AIO智能脚本全解析