栈应用：中缀表达式转后缀表达式

水深无声 2022-06-01 06:25 220阅读 0赞

**网上有很多关于中缀转后缀的文章，很多文章或多或少都有bug**，包括一些教学视频，**经过本人无数次测试，保证下面的代码运算结果的正确性**！**前提是你写的中缀表达式是正确的哈，没有做中缀表达式是否正确的的完整性校验**。采用的c语言编写的哈。

#    中缀、后缀表达式区别 #

**中缀表达式**：（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的**算术表示方法**。

**后缀表达式：后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）**

可以通过 **2个表达式计算的结果，证明是否转换正确**。

# 中缀、转后缀规则 #

**规则摘抄大话数据结构中的描述** ，中缀表达式转后缀表达式规则：

从左到右遍历中缀表达式的每个数字和符号，**若是数字就输出**，即成为后缀表达式的一部分；  
**若是符号**，则**判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号（乘除优先加减,）**

**则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止**。

# 中缀、转后缀规则分析 #

首先判断字符是否是数字

1.  是数字直接输出
2.  非数字再对字符进行分析
    
    1.  右括号，依次弹栈并输出符号，直到遇到(左括号
    2.  **字符优先级低于栈顶符号**，**依次弹栈**直到遇到**字符优先级高于栈顶符号**或者**遇到左括号**或者**空栈**，当前符号再才进(压)栈(**如果和栈顶符号优先级一样也要先栈顶符号也要先弹栈，因为优先级一样运算顺序是从左往右**！这一点很重要，很多网上的文章或者视频 都是这一点出错了！)
        
        1.  **+  - 符号是优先级最低的，一定是先依次弹栈再压栈**。
        2.  **\* / 符号优先级只比 + - 高，栈空或栈顶为( + - 符号栈才直接压栈，其他情况先依次弹栈再压栈**
    3.  左括号，**左括号(直接压栈，如果栈顶元素为左括号(，该字符同样直接压栈！这点很重要！**

# 中缀、转后缀函数局部代码 #

将用户输入放到一个字符串，将转换得到后缀表达式同样放到一个字符串中，方便封装进行复用。

/*
    将中缀表达式转成后缀表达式 
    */ 
    char* MidExpToAfterExp(const char* midExp)
    {
    	//后缀表达式
    	char* afterExp = (char*)malloc(sizeof(char)*EXPRESS_MAX);
    	memset(afterExp, 0, EXPRESS_MAX);
    	int j = 0;//afterExp下标
    	int k = 0;//preExp下标
    
    	SeqStack stack;// + - * / ( ）符号栈
    	InitStack(&stack);
    
    	char numBuf[10] = { 0 };//连续的数字不能超过10位，也就是中缀表达式中数字不能超过10位
    	char ch = 0;
    	int numIndex = 0;//numBuf 下标
    	while (midExp[k])
    	{
    		ch = midExp[k++];
    		//忽略中缀表达式中的空格
    		if (ch == ' ')
    		{
    			continue;
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//1、若是数字就输出
    		if (ch >= '0' && ch <= '9')
    		{
    			//如果输入连续的数字，不是连续的数字 循环完毕 会走 2、非数字
    			while (((ch >= '0' && ch <= '9') || '.' == ch) && numIndex < 10)
    			{
    				numBuf[numIndex++] = ch;
    				afterExp[j++] = ch;
    				ch = midExp[k++];
    			}
    			numBuf[numIndex] = 0;
    			afterExp[j++] = ' ';
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//忽略中缀表达式中的空格
    		else if (' ' == ch)
    		{
    			continue;
    		}
    		//2、非数字
    		else if (ch < '0' || ch > '9')
    		{
    			numIndex = 0;//进入这个if 数字肯定不连续了，下标重置为0
    			//右括号一定弹栈
    			if (')' == ch)
    			{
    				int flag = 1;//判断中缀表达式中括号是否匹配,如果成对出现
    				while (!IsEmptyStack(&stack))
    				{
    					pop(&stack, &ch);
    					if ('(' == ch)
    					{
    						flag = 0;//走到这里说明是()括号成对出现
    						break;
    					}
    					afterExp[j++] = ch;
    					afterExp[j++] = ' ';
    				}
    				if (flag)
    				{
    					printf("中缀表达式输入错误\n");
    					exit(0);
    				}
    
    			}
    			// + - 符号是优先级最低的，一定是先依次弹栈再压栈。
    			else if ('+' == ch || '-' == ch)
    			{
    				EleType top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号 直接压栈
    				if (IsEmptyStack(&stack)|| '(' == top)
    				{
    					push(&stack, ch);
    				}
    				else
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch)
    						{
    							//不是因为)右括号而弹栈，多弹的(左括号压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    
    					push(&stack, cur);
    				}
    			}
    			// * / 符号优先级只比 + -高，栈空或栈顶为(+-符号栈才直接压栈，其他情况先依次弹栈再压栈
    			else if ('*' == ch || '/' == ch)
    			{
    				EleType top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号同样直接压栈
    				if (IsEmptyStack(&stack) || '(' == top || '-' == top || '+' == top)
    				{
    					push(&stack, ch);
    				}
    				else if ('*' == top || '/' == top)
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch || '-' == ch || '+' == ch)
    						{
    							//不是因为)右括号而弹栈 * / 优先级高于栈顶 + - 就不弹栈了，多弹的压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    					push(&stack, cur);
    				}
    			} 
    			else if ( '(' == ch)
    			{
    				push(&stack, ch);
    			}
    			else
    			{
    				printf("中缀表达式输入错误\n");
    				exit(0);
    			}
    		}
    
    	}
    	//符号栈内容不为空 依次出栈并打印
    	while (!IsEmptyStack(&stack))
    	{
    		pop(&stack, &ch);
    		afterExp[j++] = ch;
    		afterExp[j++] = ' ';
    	}
    	return afterExp;
    }

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define STACK_INIT_SIZE 20	 // 栈初始容量
    #define STACK_INCREMENT 10   //栈满后，每次扩充的容量
    #define EXPRESS_MAX 1024 //后缀表达式 长度不能超过1024
    typedef int Status;
    typedef char EleType;
    
    typedef struct SeqStack
    {
    	EleType* top;//栈顶指针
    	EleType* base;//栈底指针
    	int stackSize;//栈容量
    }SeqStack;
    //初始化栈
    Status InitStack(SeqStack* stack)
    {
    	//开辟空间
    	stack->base = stack->top = (EleType*)malloc(STACK_INIT_SIZE * sizeof(EleType));
    	if (!stack->base)
    	{
    		exit(0);
    	}
    	stack->stackSize = STACK_INIT_SIZE;
    	return OK;
    }
    //压栈
    Status push(SeqStack* stack, EleType e)
    {
    	if (stack == NULL)
    	{
    		return ERROR;
    	}
    	//压栈之前检测容量是否足够
    	if (stack->top - stack->base == stack->stackSize)
    	{
    		//超出容量 进行扩容，使用realloc函数，会拷贝原内存内容
    		stack->base = (EleType*)realloc(stack->base, stack->stackSize + STACK_INCREMENT);
    		if (!stack->base)
    		{
    			exit(0);
    		}
    		stack->top = stack->base + stack->stackSize;
    		stack->stackSize += STACK_INCREMENT;
    	}
    	*stack->top = e;
    	stack->top++;
    	return OK;
    }
    //弹栈
    Status pop(SeqStack* stack, EleType *e)
    {
    	if (stack == NULL || e == NULL)
    	{
    		return ERROR;
    	}
    	//空栈
    	if (stack->top == stack->base)
    	{
    		return ERROR;
    	}
    	*stack->top--;
    	*e = *stack->top;
    	return OK;
    }
    /*
    获取栈顶元素
    */
    Status GetTop(SeqStack* stack, EleType *e) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	*e = *(stack->top - 1);
    	return OK;
    }
    /*
    判断栈是否为空
    */
    int IsEmptyStack(SeqStack* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	if (stack->top == stack->base) {
    		return TRUE;
    	}
    	return FALSE;
    }
    /*
    销毁栈
    */
    Status DestroyStack(SeqStack* stack)
    {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	//销毁栈 是释放栈在内存中占用的空间资源
    	if (!stack->base)
    	{
    		free(stack->base);
    	}
    	stack->top = stack->base = NULL;
    	stack->stackSize = 0;
    	return OK;
    }
    /*
    将中缀表达式转成后缀表达式 
    */ 
    char* MidExpToAfterExp(const char* midExp)
    {
    	//后缀表达式
    	char* afterExp = (char*)malloc(sizeof(char)*EXPRESS_MAX);
    	memset(afterExp, 0, EXPRESS_MAX);
    	int j = 0;//afterExp下标
    	int k = 0;//preExp下标
    
    	SeqStack stack;// + - * / ( ）符号栈
    	InitStack(&stack);
    
    	char numBuf[10] = { 0 };//连续的数字不能超过10位，也就是中缀表达式中数字不能超过10位
    	char ch = 0;
    	int numIndex = 0;//numBuf 下标
    	while (midExp[k])
    	{
    		ch = midExp[k++];
    		//忽略中缀表达式中的空格
    		if (ch == ' ')
    		{
    			continue;
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//1、若是数字就输出
    		if (ch >= '0' && ch <= '9')
    		{
    			//如果输入连续的数字，不是连续的数字 循环完毕 会走 2、非数字
    			while (((ch >= '0' && ch <= '9') || '.' == ch) && numIndex < 10)
    			{
    				numBuf[numIndex++] = ch;
    				afterExp[j++] = ch;
    				ch = midExp[k++];
    			}
    			numBuf[numIndex] = 0;
    			afterExp[j++] = ' ';
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//忽略中缀表达式中的空格
    		else if (' ' == ch)
    		{
    			continue;
    		}
    		//2、非数字
    		else if (ch < '0' || ch > '9')
    		{
    			numIndex = 0;//进入这个if 数字肯定不连续了，下标重置为0
    			//右括号一定弹栈
    			if (')' == ch)
    			{
    				int flag = 1;//判断中缀表达式中括号是否匹配,如果成对出现
    				while (!IsEmptyStack(&stack))
    				{
    					pop(&stack, &ch);
    					if ('(' == ch)
    					{
    						flag = 0;//走到这里说明是()括号成对出现
    						break;
    					}
    					afterExp[j++] = ch;
    					afterExp[j++] = ' ';
    				}
    				if (flag)
    				{
    					printf("中缀表达式输入错误\n");
    					exit(0);
    				}
    
    			}
    			// + - 符号是优先级最低的，一定是先依次弹栈再压栈。
    			else if ('+' == ch || '-' == ch)
    			{
    				EleType top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号 直接压栈
    				if (IsEmptyStack(&stack)|| '(' == top)
    				{
    					push(&stack, ch);
    				}
    				else
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch)
    						{
    							//不是因为)右括号而弹栈，多弹的(左括号压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    
    					push(&stack, cur);
    				}
    			}
    			// * / 符号优先级只比 + -高，栈空或栈顶为(+-符号栈才直接压栈，其他情况先依次弹栈再压栈
    			else if ('*' == ch || '/' == ch)
    			{
    				EleType top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号同样直接压栈
    				if (IsEmptyStack(&stack) || '(' == top || '-' == top || '+' == top)
    				{
    					push(&stack, ch);
    				}
    				else if ('*' == top || '/' == top)
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch || '-' == ch || '+' == ch)
    						{
    							//不是因为)右括号而弹栈 * / 优先级高于栈顶 + - 就不弹栈了，多弹的压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    					push(&stack, cur);
    				}
    			} 
    			else if ( '(' == ch)
    			{
    				push(&stack, ch);
    			}
    			else
    			{
    				printf("中缀表达式输入错误\n");
    				exit(0);
    			}
    		}
    
    	}
    	//符号栈内容不为空 依次出栈并打印
    	while (!IsEmptyStack(&stack))
    	{
    		pop(&stack, &ch);
    		afterExp[j++] = ch;
    		afterExp[j++] = ' ';
    	}
    	return afterExp;
    }
    
    int main(int argc, char *argv[])
    {
    	while (1)
    	{
    		printf("请输入中缀表达式(#表示退出)：");
    
    		//中缀表达式
    		char* midExp = (char*)malloc(sizeof(char)*EXPRESS_MAX) ;
    		memset(midExp, 0, EXPRESS_MAX);
    		fgets(midExp, 1024, stdin);//midExp 包含换行符
    		if ('#' == midExp[0])
    		{
    			break;
    		}
    
    		//后缀表达式
    		char* afterExp= MidExpToAfterExp(midExp);
    		printf("对应的后缀表达式：%s\n", afterExp);
    	}
    
    	return 0;
    }

# 验证结果 #

进行复杂性验证哈，确保程序正确性。如何验证正确性呢？请看 后缀表达式运算规则，如**果根据后缀表达式 的计算结果和中缀表达式计算结果一致就说明转换正确**。**如果不正确，你来找我**。

![Center][]

[Center]: /images/20220601/b0b54ac81f184863b6ea08493be9b2a7.png