数据结构之线性表——中缀表达式和后缀表达式（栈的应用）

墨蓝 2022-05-29 10:54 180阅读 0赞

1 中缀表达式

中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。  
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

举例：  
(3 + 4) × 5 - 6 就是中缀表达式  
3 4 + 5 × 6 - 后缀表达式

2 后缀表达式

不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) \* 3 ， 即2 1 + 3 \*

3 中缀表达式转后缀表达式

中缀转后缀的算法  
遍历表达式中的数字和符号

对于数字：直接输出

对于符号：  
左括号：进栈  
运算符号：与栈顶元素进行优先级比较  
 若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）  
 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈  
右括号：将栈顶符号弹出并输出  
遍历结束：将栈中所有符号弹出并输出

中缀转后缀

![Image 1][]

代码实现：其中[LinkStack.h][] [LinkStack.][LinkStack.h]c的内容参考[点击打开链接][Link 1]

/*中缀转后缀的算法
    遍历表达式中的数字和符号
    对于数字：直接输出
    对于符号：
    左括号：进栈
    运算符号：与栈顶元素进行优先级比较
    若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
    若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
    右括号：将栈顶符号弹出并输出
    遍历结束：将栈中所有符号弹出并输出
    中缀转后缀
    */
    /*
    基础知识：
    但是，平时使用的时候建议加上#include<string.h>（尤其在以下情况下）
    1、使用string类型
    2、使用cin、cout语句来输入输出string类型变量（注意，同时还需要 #include<iostream>）
    3、使用memset()、strlen()、strcpy()等函数时
    
    只要用到stdio里面定义的库函数，就要包含它
    这些库函数包括scanf，printf等等
    
    是引用stdlib.h头文件，即#include <stdlib.h>。这里的.h是不可缺少的。
    stdlib.h中，包含了C语言的一些常用库函数。如
    动态内存相关的malloc, realloc,zalloc,calloc,free等。
    随机数相关的rand,srand等。
    系统相关的system, getenv,setenv等。
    字符串转数值函数，atoi, atof,strtoul等。
    如果在代码中，调用了这个头文件中的函数或者宏定义，则需要引用该头文件。
    */
    #include "LinkStack.h"
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    int isNumber(char c)
    {
    	return ('0' <= c)&&(c <= '9');
    }
    
    int isOperator(char c)
    {
    	return ('+' == c) || (c == '-') || (c == '*') || (c == '/');
    }
    
    int isRight(char c)
    {
    	return (')' == c);
    }
    
    int isLeft(char c)
    {
    	return ('(' == c);
    }
    
    //比较优先级
    int  priority(char c)
    {
    	int ret = 0;
    	if (('+' == c) || (c == '-'))
    	{
    		ret = 1;
    	}
    	if ((c == '*') || (c == '/'))
    	{
    		ret = 2;
    	}
    	return ret;
    }
    void output(char c)
    {
    	if (c!='\0')
    	{
    		printf("%c ",c);
    	}
    }
    
    void transform(const char *exp)
    {
    	int i = 0;
    	//初始化一个空栈 此栈用来对要运算的数字进出使用
    	LinkStack *stack = LinkStack_Create();
    	if (NULL == stack)
    	{
    		printf("func err LinkStack_Create()");
    	}
    	//遍历表达式中的数字和符号
    	while (exp[i]!='\0')
    	{
    		//对于数字：直接输出
    		if (isNumber(exp[i]))
    		{
    			output(exp[i]);
    		}
    		//对于符号：
    		//左括号：进栈
    		//运算符号：与栈顶元素进行优先级比较
    		//若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
    		//若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
    		//右括号：如果遇到一个右括号，那么就将栈元素弹出 将符号写出直到遇到一个对应的左括号，但是这个左括号只被弹出 并不输出
    		//遍历结束：将栈中所有符号弹出并输出
    		else if (isOperator(exp[i]))
    		{
    			//若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
    			while (LinkStack_Size(stack) > 0 &&priority(exp[i]) <= priority((char)(int)LinkStack_Top(stack)))
    			{
    				output((char)(int)LinkStack_Pop(stack));
    			}
    			//若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
    			LinkStack_Push(stack,(void *)exp[i]);
    		}
    		//左括号：进栈
    		else if (isLeft(exp[i]))
    		{
    			LinkStack_Push(stack, (void *)exp[i]);
    		}
    		//右括号：如果遇到一个右括号，那么就将栈顶元素弹出并输出 
    		//直到遇到一个栈顶元素对应的左括号，但是这个左括号只被弹出 并不输出
    		else if (isRight(exp[i]))
    		{
    			// 如果遇到一个右括号，那么就将栈顶元素弹出并输出
    			while (!isLeft((char)(int)LinkStack_Top(stack)))
    			{
    				output((char)(int)LinkStack_Pop(stack));
    			}
    			//直到遇到一个栈顶元素对应的左括号，但是这个左括号只被弹出 并不输出
    			LinkStack_Pop(stack);
    		}
    		else
    		{
    			printf("Invalid expression!");
    			break;
    		}
    		i++;
    	}
    	//遍历结束：将栈中所有符号弹出并输出
    	while (LinkStack_Size(stack) > 0 && (exp[i] == '\0'))
    	{
    		output((char)(int)LinkStack_Pop(stack));
    	}
    	LinkStack_Destroy(stack);
    }
    void main()
    {
    	transform("8+(3-1)*5");
    
    	system("pause");
    	return;
    }

**4 后缀表达式的计算**

遍历后缀表达式中的数字和符号

对于数字：进栈

对于符号：

从栈中弹出右操作数

从栈中弹出左操作数

根据符号进行运算

将运算结果压入栈中

遍历结束：栈中的唯一数字为计算结果

![Image 1][]

代码实现：其中[LinkStack.h][] [LinkStack.c][LinkStack.h] 的内容参照上文

#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include "LinkStack.h"
    /*
    遍历后缀表达式中的数字和符号
    对于数字：进栈
    对于符号：
    从栈中弹出右操作数
    从栈中弹出左操作数
    根据符号进行运算
    将运算结果压入栈中
    遍历结束：栈中的唯一数字为计算结果
    */
    
    int isNumber(char c)
    {
    	return ('0' <= c) && (c <= '9');
    }
    
    int isOperator(char c)
    {
    	return (c == '+') || (c == '-') || (c == '*') || (c == '/');
    }
    //字符中数字 转成int类型 方便压入栈中
    int value(char c)
    {
    	return (c - '0');
    }
    
    int Calculation(int left,int right,char op)
    {
    	int ret = 0;
    	switch (op)
    	{
    	case '+':
    		ret = left + right;
    		break;
    	case '-':
    		ret = left - right;
    		break;
    	case '*':
    		ret = left * right;
    		break;
    	case '/':
    		ret = left / right;
    		break;
    	default:
    		break;
    	}
    	return ret;
    }
    int compute(const char *exp)
    {
    	int ret = 0;
    	//1 创建一个空栈 进行后缀表达式元运算
    	LinkStack *stack = LinkStack_Create();
    	if (NULL == stack)
    	{
    		printf("func err LinkStack_Create()\n");
    	}
    	int i = 0;
    	//2 遍历后缀表达式中的数字和符号
    	while (exp[i]!='\0')
    	{
    		//3 对于数字 进栈
    		if (isNumber(exp[i]))
    		{
    			LinkStack_Push(stack,(void *)value(exp[i]));
    		}
    		//对于符号：
    		else if (isOperator(exp[i]))
    		{
    			//从栈中弹出右操作数
    			int right = (int)LinkStack_Pop(stack);
    			//从栈中弹出左操作数
    			int left = (int)LinkStack_Pop(stack);
    			//根据符号进行运算
    			int result = Calculation(left, right, exp[i]);
    			//将运算结果压入栈中
    			LinkStack_Push(stack,(void *)result);
    		}
    		else
    		{
    			printf("Invalid expression1!");
    			break;
    		}
    		i++;
    	}
    	//遍历结束：栈中的唯一数字为计算结果
    	if((LinkStack_Size(stack) == 1) && (exp[i]=='\0'))
    	{
    		ret = (int)LinkStack_Pop(stack);
    	}
    	else
    	{
    		printf("Invalid expression!2");
    	}
    	LinkStack_Destroy(stack);
    
    	return ret;
    }
    int main()
    {
    	int ret = 0;
    	ret = compute("831-5*+");
    	printf("8 + (3 - 1) * 5  = %d\n",ret);
    	system("pause");
    	return 0;
    }

[Image 1]: 
[LinkStack.h]: http://blog.csdn.net/ds_kuen/article/details/71703584
[Link 1]: http://blog.csdn.net/weixin_40807247/article/details/79653230