补充了一个判断输入中缀表达式合法性的代码：

《数据结构》：中缀表达式合法性判断_Amentos的博客-CSDN博客

目录

一、基本概念

二、中缀表达式转后缀表达式

例 中缀表达式 2*(3+5)+7/1-4 转换为后缀表达式

三、后缀表达式的计算

例 后缀表达式 2 3 5 + * 7 1 / + 4 -的计算

四、算法实现

五、算法改进

一、基本概念

1、中缀表达式：

操作符以中缀形式位于运算数中间（如：3+2），是我们日常通用的算术和逻辑公式表示方法。

2、后缀表达式：

又称逆波兰式（Reverse Polish Notation - RPN），操作符以后缀形式位于两个运算数后（如：3+2的后缀表达形式就是3 2 +）。

3、前缀表达式：

又称波兰式（Polish Notation），操作符以前缀形式位于两个运算数前（如：3+2的前缀表达形式就是+ 3 2）。

中缀表达式往往需要使用括号将操作符和对应的操作数括起来，用于指示运算的次序

e.g：5*(2+1) 虽然*的优先级高于 +，但括号的存在表示应优先执行括号内的 + 运算。

中缀表达式适合于人类的思维结构和运算习惯，但并不适用于计算机

尤其是包含括号的中缀表达式，对计算机而言是非常复杂的结构。

适用于计算机的后缀表达式

与中缀表达式不同，后缀表达式不需要使用括号来标识操作符的优先级。

后缀表达式的计算按操作符从左到右出现的顺序依次执行(不考虑运算符之间的优先级)，对于计算机而言是比较简单的结构。

二、中缀表达式转后缀表达式

从左至右依次遍历中缀表达式各个字符（需要准备一个字符栈存储操作符和括号）

1、字符为运算数：

直接送入后缀表达式（注：需要先分析出完整的运算数）。

2、字符为左括号：

直接入栈（注：左括号入栈后优先级降至最低）。

3、字符为右括号：

直接出栈，并将出栈字符依次送入后缀表达式，直到栈顶字符为左括号（左括号也要出栈，但不送入后缀表达式）。

总结：只要满足 栈顶为左括号 即可进行最后一次出栈。

4、字符为操作符：

若栈空，直接入栈。

若栈非空，判断栈顶操作符，若栈顶操作符优先级低于该操作符，该操作符入栈；否则一直出栈，并将出栈字符依次送入后缀表达式，直到栈空或栈顶操作符优先级低于该操作符，该操作符再入栈。

总结：只要满足 栈空 或者 优先级高于栈顶操作符 即可停止出栈，并将该操作符入栈。

5、重复以上步骤直至遍历完成中缀表达式，接着判断字符栈是否为空，非空则直接出栈，并将出栈字符依次送入后缀表达式。

注：中缀表达式遍历完成，栈中可能还有字符未输出，故需要判断栈空。

例 中缀表达式 2*(3+5)+7/1-4 转换为后缀表达式

从左至右依次遍历中缀表达式各个字符：

第一个字符为运算数，直接输出：

第二个字符为操作符，满足栈空/优先级高于栈顶操作符条件，该操作符入栈：

第三个字符为左括号，直接入栈（入栈后优先级降至最低）：

第四个字符为运算数，直接输出：

第五个字符为操作符，满足 栈空/优先级高于栈顶操作符条件，该操作符入栈：

第六个字符为运算数，直接输出：

第七个字符为右括号，直接出栈并输出，直到栈顶为左括号时进行最后一次出栈(不输出)：

第八个字符为操作符，不满足 栈空/优先级高于栈顶操作符条件，出栈直至满足条件

第九个字符为运算数，直接输出：

第十个字符为操作符，满足 栈空/优先级高于栈顶操作符条件，该操作符入栈：

第十一个字符为运算数，直接输出：

第十二个字符为操作符，不满足 栈空/优先级高于栈顶操作符条件，出栈直至满足条件：

第十三个字符为运算数，直接输出：

中缀表达式遍历完成，判断字符栈中是否还有操作符，如有则出栈并输出：

转换完成：

三、后缀表达式的计算

从左至右依次遍历后缀表达式各个字符（需要准备一个运算数栈存储运算数和操作结果）

1、字符为运算数：

直接入栈（注：需要先分析出完整的运算数并将其转换为对应的数据类型）

2、字符为操作符：

连续出栈两次，使用出栈的两个数据进行相应计算，并将计算结果入栈

e.g：第一个出栈的运算数为 a ，第二个出栈的运算数为 b ，此时的操作符为 - ，则计算b-a（注：a和b顺序不能反），并将结果入栈。

3、重复以上步骤直至遍历完成后缀表达式，最后栈中的数据就是中缀表达式的计算结果。

例后缀表达式2 3 5 + * 7 1 / + 4 -的计算

从左至右依次遍历后缀表达式各个字符：

第一个字符为运算数，直接入栈：

第二个字符为运算数，直接入栈：

第三个字符为运算数，直接入栈：

第四个字符为操作符，直接出栈两次：

继续出栈：

执行：第二次出栈运算数 操作符 第一次出栈运算数

即：3 + 5

结果：8

将计算结果入栈：

第五个字符为操作符，直接出栈两次：

执行：第二次出栈运算数 操作符 第一次出栈运算数

即：2 *8

结果：16

将计算结果入栈：

第六个字符为运算数，直接入栈：

第七个字符为运算数，直接入栈：

第八个字符为操作符，直接出栈两次：

执行：第二次出栈运算数 操作符 第一次出栈运算数

即：7 /1

结果：7

将计算结果入栈：

第九个字符为操作符，直接出栈两次：

执行：第二次出栈运算数 操作符 第一次出栈运算数

即：16 +7

结果：23

将计算结果入栈：

第十个字符为运算数，直接入栈：

第十一个字符为操作符，直接出栈两次：

执行：第二次出栈运算数 操作符 第一次出栈运算数

即：23 -4

结果：19

将计算结果入栈：

后缀表达式遍历完成，栈中数据即为最终计算结果：

四、算法实现

程序代码：

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include<ctype.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/#define M 50typedef char ElemType; /*定义字符数据类型*/typedef double ElemType2; /*定义运算数数据类型*//*字符栈*/typedef struct{ElemType *base;ElemType *top;int stacksize; }SqStack;/*运算数栈*/typedef struct{ElemType2 *base;ElemType2 *top;int stacksize;}NStack;int InitStack(SqStack *S); /*构造空栈*/int push(SqStack *S,ElemType e); /*入栈*/int Pop(SqStack *S,ElemType *e); /*出栈*/int StackEmpty(SqStack *s); /*栈空判断*/void in2post(ElemType *str,ElemType *p); /*中缀表达式转后缀表达式*/double cal_post(char *str); /*计算后缀表达式*//*字符栈初始化*/int InitStack(SqStack *S){S->base=(ElemType *)malloc(STACK_INT_SIZE * sizeof(ElemType));if(!S->base)return ERROR; //分配失败S->top = S->base;S->stacksize = STACK_INT_SIZE;return OK;}/*InitStack*//*运算数栈初始化*/int InitStack_N(NStack *S){S->base=(ElemType2 *)malloc(STACK_INT_SIZE * sizeof(ElemType2));if(!S->base)return ERROR;S->top = S->base;S->stacksize = STACK_INT_SIZE;return OK;}/*字符栈入栈*/int Push(SqStack *S,ElemType e){//判断栈满if(S->top - S->base >= S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(ElemType));if(NULL == S->base) //分配失败return ERROR;S->top = S->base + S->stacksize;S->stacksize = S->stacksize+STACKINCREMENT;}*S->top = e;S->top++;return OK;}/*运算数栈入栈*/int Push_N(NStack *S,ElemType2 e){if(S->top - S->base >= S->stacksize){S->base = (ElemType2 *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(ElemType2));if(NULL == S->base)return ERROR;S->top = S->base + S->stacksize;S->stacksize = S->stacksize+STACKINCREMENT;}*S->top = e;S->top++;return OK;}/*字符栈出栈*/int Pop(SqStack *S,ElemType *e){//判断栈空if(S->top == S->base)return ERROR;S->top--;*e=*S->top;return OK;}/*Pop*//*运算数栈出栈*/int Pop_N(NStack *S,ElemType2 *e){if(S->top == S->base)return ERROR;S->top--;*e=*S->top;return OK;}/*判断栈空*/int StackEmpty(SqStack *s){if(s->top == s->base)return OK;return ERROR;}/*StackEmpty*///str为待转换的中缀表达式字符串,p为转换后的后缀表达式字符串void in2post(ElemType *str,ElemType *p){ /*infix to postfix*/SqStack s; InitStack(&s); //初始化一个空字符栈ElemType e;int i;int j=0;for(i=0 ; i<strlen(str) ; i++) //遍历中缀表达式{//遇到数字和小数点直接输出//使用循环完整接收一个运算数while(isdigit(str[i]) || '.'==str[i]){p[j++]=str[i++];if(!isdigit(str[i]) && '.'!=str[i])p[j++]=' '; //一个数字完整输出后使用空格与其它运算符或数字分隔开}//遇到左括号直接入栈if('('==str[i])Push(&s,str[i]);//遇到右括号直接出栈，直到栈顶为左括号if(')'==str[i]){while('(' != *(s.top-1)){Pop(&s,&e);p[j++]=e;p[j++]=' ';}Pop(&s,&e); //左括号出栈但不输出}//遇到+或—//1.栈空/栈顶为左括号:直接入栈//2.否则一直出栈,直到栈空/栈顶为左括号,再入栈if('+'==str[i] || '-'==str[i]){while(!StackEmpty(&s) && '('!=*(s.top-1)){Pop(&s,&e);p[j++]=e;p[j++]=' ';}Push(&s,str[i]);}//遇到*或///1.栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈//2.否则一直出栈,直到满足1,再入栈if('*'==str[i] || '/'==str[i] || '%'==str[i]){while(!StackEmpty(&s) && '('!=*(s.top-1) && '+'!=*(s.top-1) && '-'!=*(s.top-1)){Pop(&s,&e);p[j++]=e;p[j++]=' ';}Push(&s,str[i]);}}//中缀表达式遍历完成,还需检查栈中是否有未输出字符//判断栈空,非空则直接出栈并输出(左括号不用输出)while(!StackEmpty(&s)){Pop(&s,&e);if('('!=e){p[j++]=e;p[j++]=' ';}}p[--j]='\0';}/*infix2postfix*///str为待计算的后缀表达式,返回值为计算结果double cal_post(char *str){ /*计算后缀表达式*/int i;ElemType2 e,a,b;char d[M];NStack n;InitStack_N(&n); //初始化一个运算数栈保存运算数for(i=0;i<strlen(str);i++){int j=0;while(isdigit(str[i]) || '.'==str[i]){d[j++]=str[i++];d[j]='\0';if(!isdigit(str[i]) && '.'!=str[i]){e=atof(d); //使用atof()将字符串形式的运算数转换为double型数据Push_N(&n,e); //运算数入栈}}switch(str[i]){case '+':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a+b);break;case '-':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a-b);break;case '*':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a*b);break;case '/':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a/b);break;}}Pop_N(&n,&e);return e;}/*calculate_postfix*/int main(){char str[M];char post[M];int i;printf("\n输入一串中缀表达式：\n");gets(str);printf("\n对应的后缀表达式：\n");in2post(str,post);printf("%s",post);printf("\n\n计算后缀表达式：\n");printf("%f",cal_post(post));return 0;}

运行结果：

五、算法改进

上面的代码正确运算的前提是：

① 输入的中缀表达式合法

② 运算数非负数

例如：输入 3*(-6+5)，得到以下结果，后缀表达式和运算结果明显不正确。

这里的 -6 应该才是一个完整的运算数，但是在后缀表达式中'-' 号和数字 '6' 被拆分开来了，得到的结果也不正确。因为代码中对于 '-' 号一律是作为操作符处理，所以面对像 -6 这样的负数时不能分析出完整正确的运算数。

如果要进行修改，在进行运算数分析的时候就要考虑负数的情况。当出现 '-' 号的时候，要判断它是作为负数标志，属于运算数的一部分，还是作为一个运算符。

所以需要对运算数分析的代码添加负数的处理，修改后的代码如下：

in2post函数代码修改：

void in2post(ElemType *str,ElemType *p){ /*infix to postfix*///初始化一个空栈SqStack s;InitStack(&s);ElemType e;int i;int j=0;for(i=0 ; i<strlen(str) ; i++) //遍历中缀表达式{if('-' == str[i]) //负数情况判断{//表达式首位是'-',则一定是作为负数符号if(0 == i)p[j++]=str[i++];//'-'前面是'(',则一定是作为负数符号else if('(' == str[i-1])p[j++]=str[i++];}//遇到数字和小数点直接输出while(isdigit(str[i]) || '.'==str[i]){p[j++]=str[i++];if(!isdigit(str[i]) && '.'!=str[i])p[j++]=' '; //一个数字完整输出后使用空格与其它运算符或数字分隔开}//遇到左括号直接入栈if('('==str[i])Push(&s,str[i]);//遇到右括号直接出栈，直到左括号出栈(左括号不输出)if(')'==str[i]){while('(' != *(s.top-1)){Pop(&s,&e);p[j++]=e;p[j++]=' ';}Pop(&s,&e); //左括号出栈但不输出}//遇到+或—//1.栈空/栈顶为左括号:直接入栈//2.否则一直出栈,直到栈空/栈顶为左括号,再入栈if('+'==str[i] || '-'==str[i]){while(!StackEmpty(&s) && '('!=*(s.top-1)) //栈非空 且 栈顶非左括号{Pop(&s,&e);p[j++]=e;p[j++]=' ';}Push(&s,str[i]);}//遇到*或///1.栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈//2.否则一直出栈,直到满足1,再入栈if('*'==str[i] || '/'==str[i] || '%'==str[i]){while(!StackEmpty(&s) && '('!=*(s.top-1) && '+'!=*(s.top-1) && '-'!=*(s.top-1)){Pop(&s,&e);p[j++]=e;p[j++]=' ';}Push(&s,str[i]);}}//中缀表达式遍历完成,还需检查栈中是否有未输出字符//判断栈空,非空则直接出栈并输出(左括号不用输出)while(!StackEmpty(&s)){Pop(&s,&e);if('('!=e){p[j++]=e;p[j++]=' ';}}p[--j]='\0';}

cal_post函数代码修改：

double cal_post(char *str){ElemType2 e,a,b;char d[M];//初始化一个运算数栈保存运算数NStack n;InitStack_N(&n);int i=0;int j=0;while(str[i]) //遍历后缀表达式{switch(str[i]){case '-':if( isdigit(str[i+1]) ) //判断'-'是作为负数符号or运算符{d[j++]=str[i++]; //将负号加入运算数字符串d[j]='\0';break; //注:这里的break只是跳出switch循环}else{Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a-b);i++;break;}case '+':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a+b);i++;break;case '*':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a*b);i++;break;case '/':Pop_N(&n,&b);Pop_N(&n,&a);Push_N(&n,a/b);i++;break;case ' ':i++;}//遇到运算数直接入栈(先转换double类型)//d保存后缀表达式中的字符串形式的运算数//使用atof将字符串转换为double类型while(isdigit(str[i]) || '.'==str[i]){d[j++]=str[i++];d[j]='\0';if( ' ' == str[i] ){e = atof(d); //此时分析出的就是完整的运算数Push_N(&n,e);i++;j = 0;}}}Pop_N(&n,&e);return e;}

运行结果：