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

目录一、基本概念1. 中缀表达式2. 后缀表达式二、算法转换思想1.中缀转后缀表达式2.后缀转中缀表达式三、转换实现1.中缀转后缀表达式实现代码实现图解详情2.后缀转中缀表达式实现代码实现图解详情四、整体实现过程1.中缀转后缀表达式2.后缀转中缀表达式一、基本概念1. 中缀表达式基本概念运算符放在两个操作数中间这是我们常用的数学表达式有括号和优先级。例ab、5∗(3−2)、1020/5特点依靠括号、运算符优先级、结合性决定计算顺序。2. 后缀表达式运算符放在两个操作数后面这是为了访问计算机栈的运算无括号、无优先级。例 ab中缀 → 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/256*-; //获取字符 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/256*-; //初始化 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; }