中缀，后缀，前缀表达式的计算以及转化详解

数据结构正好学到栈，中缀，前缀，后缀表达式把人绕的不行，写一个博客也算是总结一下这5个算法：中缀表达式的计算，中缀表达式转后缀表达式，后缀表达式计算，中缀表达式转前缀表达式，前缀表达式计算

中缀表达式的计算

思路： 首先设立两个栈，一个operator（运算符）栈，一个operand（运算数）栈。输入数字进入operand栈，输入运算符进入operator栈，表达式以’#‘开始和结束。 对于字符进栈，需要比较当前输入的字符和operator栈顶字符的优先级大小：若当前运算符优先级高于栈顶运算符，则当前运算符进栈；若当前运算符优先级低于栈顶运算符，则栈顶运算符出栈，并且operand栈顶的两个运算符也出栈，三者进行运算后的结果再次存入operand运算数栈。此时的当前运算符再继续和栈顶运算符比较，直到优先级大于栈顶运算符为止。 当两个’#'相遇时，也就是表达式结束是，读取operand栈的栈顶元素的值，即为中缀表达式的值。

代码共设12个函数： （1）两个栈的基本操作6个函数：Init(),Push(),Pop() （2）判断字符是否为数字的函数 In(char ch) （3）获取数字栈栈顶元素的函数GetTop1(Operand S) （4）获取运算符栈栈顶元素的函数GetTop2(Operator S) （5）比较栈顶运算符和当前运算符优先级的函数Compare(Operator S,char ch) （6）计算pop出的运算符和两个运算数的函数Execute(int a,int b,char op) （7）计算中缀表达式的值的函数 ExpEvaluation()

在这里我使用了一个二维数组来存储运算符的优先级，需要注意的是要搞清行和列哪一个是当前运算符，哪一个是栈顶运算符

#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #define MAXSIZE 100 char A[7] = {'+','-','*','/','(',')','#'}; char B[7][7] = { {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','!'}, {'>','>','>','>','!','>','>'}, {'<','<','<','<','<','!','='} }; typedef struct { int* elem; int top; }Operand;//运算数栈 typedef struct { char* elem; int top; }Operator;//运算符栈 void Init_Operand(Operand* S)//初始化数字栈 { S->elem = (int*)malloc(sizeof(int)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push_Operand(Operand* S,int x)//数字x进栈 { if(S->top == MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = x; printf("%d\n",S->elem[S->top]); printf("入栈成功!\n"); } } void Pop_Operand(Operand* S,int *x)//数字出栈，将值存储在x中 { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *x = S->elem[S->top]; S->top--; printf("%d\n",*x); printf("出栈成功!\n"); } } void Init_Operator(Operator* S)//初始化运算符栈 { S->elem = (char*)malloc(sizeof(char)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push_Operator(Operator* S,char ch)//运算符ch进栈 { if(S->top == MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = ch; printf("%c",S->elem[S->top]); printf("进栈成功!\n"); } } void Pop_Operator(Operator* S,char* ch)//运算符ch出栈，将值储存在ch中 { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *ch = S->elem[S->top]; S->top--; printf("%c",*ch); printf("出栈成功!\n"); } } bool In(char ch)//判断字符ch是否为数字，不是的话返回true，是的话返回false { for(int i=0;i<7;i++) { if(ch == A[i]) return true; } return false; } int GetTop1(Operand S)//获取数字栈栈顶运算符的值 { int x; x = S.elem[S.top]; return x; } char GetTop2(Operator S)//获取字符栈栈顶运算符的值 { char ch; ch = S.elem[S.top]; return ch; } char Compare(Operator S,char ch)//比较栈顶运算符和当前运算符的优先级 { int temp1,temp2; char c = GetTop2(S);//获取栈顶运算符 for(int i=0;i<7;i++) { if(c==A[i]) temp1 = i;//获取二维数组的行坐标 if(ch==A[i]) temp2 = i;//获取二维数组的列坐标 } return B[temp1][temp2]; } int Execute(int a,int b,char op)//b是先弹出的，a是后弹出的 { int v; switch(op) { case '+':v = a+b;break; case '-':v = a-b;break; case '*':v = a*b;break; case '/':v = a/b;break; } return v; } void ExpEvaluation() { int value; char ch,op,x; int a,b; Operand s1; Operator s2; Init_Operand(&s1);//初始化数字栈 Init_Operator(&s2);//初始化字符栈 Push_Operator(&s2,'#'); ch = getchar(); while(ch!='#'||GetTop2(s2)!='#') { if(!In(ch))//不是执行运算符if { ch = ch - '0'; Push_Operand(&s1,ch); fflush(stdin);//清空缓冲区 ch = getchar(); } else { switch(Compare(s2,ch)) { case '<': //栈顶运算符优先级低于当前运算符,入栈 { Push_Operator(&s2,ch); fflush(stdin); ch = getchar(); }break; case '>': //栈顶运算符优先级高于当前运算符,出栈 { Pop_Operator(&s2,&op); Pop_Operand(&s1,&b); Pop_Operand(&s1,&a); value = Execute(a,b,op); Push_Operand(&s1,value); }break; case '=': { Pop_Operator(&s2,&x); fflush(stdin); ch = getchar(); }break; } } } value = GetTop1(s1); printf("中缀表达式的值为:%d",value); } int main() { ExpEvaluation(); return 0; }

中缀表达式转后缀表达式并计算

思路： 设立一个运算符栈operator和一个字符数组，字符数组用来存储需要输出的字符（包括数字和运算符），operator栈用来比较当前运算符和栈顶运算符的优先级大小。同样表达式以‘#’开头和结尾。 输入若为数字直接存入字符数组，若为运算符则压入operator栈中，在入栈时，若当前运算符的优先级高于operator栈顶运算符，则当前运算符入栈；若当前运算符优先级低于operator栈顶运算符，则栈顶运算符出栈，进入字符数组中，当前运算符再继续与此时的栈顶运算符进行比较，直到当前运算符的优先级大于栈顶运算符为止。 对于括号，左括号‘(’直接入栈，当遇到右括号’)'时，不管优先级，开始将栈顶运算符按上面规律弹出，直到遇到左括号，将左括号弹出，然后读取下一个字符。 后缀表达式的计算很简单，只需要建立一个operand栈，当遇到数字则入栈，遇到字符，则弹出栈顶的两个元素进行计算后将结果入栈，依次循环。 代码如下：

#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #define MAXSIZE 100 char A[7] = {'+','-','*','/','(',')','#'}; char B[7][7] = { {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','!'}, {'>','>','>','>','!','>','>'}, {'<','<','<','<','<','!','='} }; typedef struct { char* elem; int top; }Operator;//存储运算符的栈operator typedef struct { char *elem; int top; }Array;//定义一个数组的结构体类型，用来存储字符 typedef struct { int* elem; int top; }Operand;//用来计算后缀表达式的值的数字栈 void Init_Operator(Operator* S) { S->elem = (char*)malloc(sizeof(char)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push(Operator* S,char ch) { if(S->top == MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = ch; printf("%c\n",S->elem[S->top]); printf("入栈成功!\n"); } } void Pop(Operator* S,char* ch) { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *ch = S->elem[S->top]; S->top--; printf("%c\n",*ch); printf("出栈成功!\n"); } } void Init_Array(Array* A)//初始化字符数组 { A->elem = (char*)malloc(sizeof(char)*MAXSIZE); A->top = -1; if(A->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Add(Array* A,char ch)//因为只需要向字符数组中加入元素，故之定义add() { if(A->top==MAXSIZE) { printf("栈满!\n"); exit(-1); } else { A->top++; A->elem[A->top] = ch; printf("%c ",A->elem[A->top]); printf("入栈成功!\n"); } } void Init_Operand(Operand* S)//初始化数字栈 { S->elem = (int*)malloc(sizeof(int)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push_Operand(Operand* S,int x) { if(S->top==MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = x; printf("%d ",S->elem[S->top]); printf("内存分配成功!\n"); } } void Pop_Operand(Operand* S,int *x) { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *x = S->elem[S->top]; S->top--; printf("%d\n",*x); printf("出栈成功!\n"); } } bool In(char ch)//是字符返回true,是数字返回false { for(int i=0;i<7;i++) { if(ch==A[i]) return true; } return false; } char GetTop(Operator S) { char ch; ch = S.elem[S.top]; return ch; } int Execute(int a,int b,char op) { int v; switch(op) { case '+':v = a+b;break; case '-':v = a-b;break; case '*':v = a*b;break; case '/':v = a/b;break; } return v; } char Compare(char ch,Operator S) { int temp1,temp2; char c; c = GetTop(S); for(int i=0;i<7;i++) { if(c==A[i]) temp1 = i; if(ch==A[i]) temp2 = i; } return B[temp1][temp2]; } void print(char ch) { if(In(ch))//是字符执行if语句 printf("%c ",ch); else printf("%d ",ch); } void print_Array(Array A) { for(int i=0;i<=A.top;i++) { printf("%c",A.elem[i]); } } void Calcul_Exp(Array A)//后缀表达式的计算 { int a,b,value; //char temp; Operand Stack; Init_Operand(&Stack); for(int i=0;i<=A.top;i++) { if(!In(A.elem[i]))//是数字，入栈 { A.elem[i] = A.elem[i] - '0'; Push_Operand(&Stack,A.elem[i]); } else//字符,故 pop it { Pop_Operand(&Stack,&b); Pop_Operand(&Stack,&a); value = Execute(a,b,A.elem[i]); Push_Operand(&Stack,value); } } Pop_Operand(&Stack,&value); printf("后缀表达式的值为:%d",value); } void Transfer() { char ch,op; Operator Stack; Array A; Init_Array(&A); Init_Operator(&Stack); Push(&Stack,'#'); ch = getchar(); while(ch!='#') { if(!In(ch))//不是字符 { Add(&A,ch); fflush(stdin); ch = getchar(); } else//是字符 { switch(Compare(ch,Stack)) { case '<'://栈顶运算符优先级低于当前运算符 { Push(&Stack,ch); fflush(stdin); ch = getchar(); }break; case '>'://栈顶运算符的优先级高于当前运算符 { if(GetTop(Stack)==')') Pop(&Stack,&op); else { Pop(&Stack,&op); Add(&A,op); } }break; case '=': { Pop(&Stack,&op); fflush(stdin); ch = getchar(); }break; } } } //printf("OK？\n"); while(GetTop(Stack)!='#') { Pop(&Stack,&op); Add(&A,op); } print_Array(A); Calcul_Exp(A); } int main() { Transfer(); //Calcul_Exp(); return 0; }

中缀表达式转前缀表达式

思路： 首先应建立两个数组结构体，一个用来存储输入的中缀表达式，一个用来存储转化后的前缀表达式；再应建立一个运算符operator栈，用来判定运算符的优先级大小。 首先输入中缀表达式，将中缀表达式存放在一个字符数组中，再从右至左读取中缀表达式中的字符，若为数字则直接存放入前缀表达式数组中；若为字符，则需判定该字符与operator栈栈顶字符的优先级：若该字符优先级高于栈顶运算符，则该字符入栈，若低于，则栈顶运算符出栈，该字符再与此时的栈顶运算符比较，直到其优先级高于栈顶运算符为止。 对于右括号‘)’，应压入栈中；对于左括号‘(’，应依次将栈顶运算符弹出直到遇到右括号为止‘)’，值得注意的是，左括号和右括号都不需要进入前缀表达式数组中。 注：为了简便运算，我将运算符优先级表稍作调整

代码如下：

#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #define MAXSIZE 100 char A[7] = {'+','-','*','/','(',')','#'}; char B[7][7] = {//此处对表做了一些修改 {'>','>','<','<','>','<','>'}, {'>','>','<','<','>','<','>'}, {'>','>','>','>','>','<','>'}, {'>','>','>','>','>','<','>'}, {'<','<','<','<','>','=','!'}, {'<','<','<','<','=','<','>'}, {'<','<','<','<','<','<','='} }; typedef struct { char* elem; int top; }Operator; typedef struct { char* elem; int top; }Array; void Init_Operator(Operator* S) { S->elem = (char*)malloc(sizeof(char)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push(Operator* S,char ch) { if(S->top == MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = ch; printf("%c\n",S->elem[S->top]); printf("入栈成功!\n"); } } void Pop(Operator* S,char* ch) { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *ch = S->elem[S->top]; S->top--; printf("%c\n",*ch); printf("出栈成功!\n"); } } void Init_Array(Array* A) { A->elem = (char*)malloc(sizeof(char)*MAXSIZE); A->top = -1; if(A->elem==NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Add(Array* A,char ch) { printf("这里呢?\n"); if(A->top==MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { A->top++; A->elem[A->top] = ch; printf("%c\n",A->elem[A->top]); printf("插入成功!\n"); } } bool In(char ch)//是运算符返回true,是数字返回false { for(int i=0;i<7;i++) { if(ch==A[i]) return true; } return false; } char GetTop(Operator S) { char ch; ch = S.elem[S.top]; //printf("%c\n",ch); return ch; } char Compare(char ch,Operator S) { char c; int temp1,temp2; c = GetTop(S); for(int i=0;i<7;i++) { if(c==A[i]) temp1 = i; if(ch==A[i]) temp2 = i; } //printf("%c\n",B[temp1][temp2]); return B[temp1][temp2]; } void print(Array A) { for(int i=A.top;i>=0;i--) { printf("%c",A.elem[i]); } } void Transfer() { char ch,op,temp; Array A1,A2; int i=0; Operator Stack; Init_Array(&A1); Init_Array(&A2); Init_Operator(&Stack); Push(&Stack,'#'); printf("请输入中缀表达式:\n"); ch = getchar(); while(ch!='#') { Add(&A1,ch); fflush(stdin); ch = getchar(); i = A1.top; } print(A1); while(i>=0) { if(!In(A1.elem[i]))//是数字执行if语句 { printf("第二步?\n"); temp = A1.elem[i]; Add(&A2,temp); i--; } else { switch(Compare(A1.elem[i],Stack)) { case '<'://栈顶运算符优先级低于当前运算符 { Push(&Stack,A1.elem[i]); i--; }break; case '>'://栈顶运算符优先级高于当前运算符 { Pop(&Stack,&op); Add(&A2,op); }break; case '=': { Pop(&Stack,&op); i--; }break; } } } while(GetTop(Stack)!='#') { Pop(&Stack,&op); Add(&A2,op); printf("%c\n",op); } print(A2); } int main() { Transfer(); return 0; }

前缀表达式的计算

思路： 首先建立一个operand栈，由于将中缀表达式转换为前缀后是将其存储在一个字符数组中的，则从左向右读取该数组中的元素，遇到数字进入operand栈，遇到运算符，则将栈顶的两个元素依次弹出与该运算符进行计算，结果再入operand栈。当前缀表达式数组扫描完成后，则operand栈顶的元素值即为前缀表达式的值。 代码：

//将这些语句插入上面代码即可运行 typedef struct { int* elem; int top; }Operand; void Init_Operand(Operand* S) { S->elem = (int*)malloc(sizeof(int)*MAXSIZE); S->top = -1; if(S->elem == NULL) { printf("内存分配失败!\n"); exit(-1); } else printf("内存分配成功!\n"); } void Push_Operand(Operand* S,int x) { if(S->top==MAXSIZE-1) { printf("栈满!\n"); exit(-1); } else { S->top++; S->elem[S->top] = x; printf("%d ",S->elem[S->top]); printf("内存分配成功!\n"); } } void Pop_Operand(Operand* S,int *x) { if(S->top<0) { printf("栈空!\n"); exit(-1); } else { *x = S->elem[S->top]; S->top--; printf("%d\n",*x); printf("出栈成功!\n"); } } int Execute(int a,int b,char op) { int v; switch(op) { case '+':v = a+b;break; case '-':v = a-b;break; case '*':v = a*b;break; case '/':v = a/b;break; } return v; } void Calcul_Exp(Array A) { int a,b,value; Operand S; Init_Operand(&S); for(int i=0;i<=A.top;i++) { if(!In(A.elem[i]))//是数字执行if语句 { A.elem[i] = A.elem[i] - '0'; //printf("%d\n",A.elem[i]); //exit(-1); Push_Operand(&S,A.elem[i]); } else { Pop_Operand(&S,&b); Pop_Operand(&S,&a); value = Execute(a,b,A.elem[i]); Push_Operand(&S,value); } } Pop_Operand(&S,&value); printf("前缀表达式的值为:%d",value); }