- 补充了一个判断输入中缀表达式合法性的代码：
《数据结构》：中缀表达式合法性判断_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 #include #include #include #include #define ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ #define M 50 typedef 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
