[数据结构]栈实现中缀表达式转换为逆波兰表达式并计算

迈不过友情╰ 2022-11-18 02:27 209阅读 0赞

### 目录 ###

*  一. 概述
 *   *  1. 什么是中缀表达式
     *  2.什么是逆波兰表达式
     *  3.为什么需要逆波兰表达式
 *  二. 实现原理
 *   *  1. 中缀表达式转换为逆波兰表达式
     *   *  1). 基本思路
         *  2). 方法详解
     *  2. 利用逆波兰表达式进行计算
     *   *  1). 基本思路
 *  三. 代码实现
 *   *  1.将中缀表达式转换为逆波兰表达式
     *  2. 利用逆波兰表达式计算

# 一. 概述 #

## 1. 什么是中缀表达式 ##

中缀表达式，是我们最熟知的一种数学表达式。

例如：1+2*(3-2);

## 2.什么是逆波兰表达式 ##

逆波兰表达式也叫后缀表达式，这种表达式没有括号，利用栈先进后出的特性进行对数据进行计算。

例如：1+2*(3-2) 的逆波兰表达式为 1 2 3 2 - * +

## 3.为什么需要逆波兰表达式 ##

中缀表达式是一种利于我们人类进行计算的表达式，但是计算机处理起中缀表达式相当复杂，所以我们将中缀表达式转换为逆波兰表达式，使计算机不用想人脑一样考虑运算符优先级和括号的情况。

# 二. 实现原理 #

关于栈的基本操作就不在此篇文章进行赘述，可点击至此处 [栈的基本操作][Link 1] 进行跳转。

## 1. 中缀表达式转换为逆波兰表达式 ##

在此篇文章中，利用堆栈的方法进行转换。

### 1). 基本思路 ###

中缀表达式中，可以将表达式中的元素分为两个部分，一是操作数，二是运算符。只需要对着两种元素进行处理即可。

### 2). 方法详解 ###

以 1+2\*(3-2) 进行举例。根据运算符的优先级进行转换。

1.  如果遇到的元素为操作数，则将该操作数直接进行存储。
2.  如果遇到的元素为操作符，则分为以下几种情况。
    
    1.  如果为 - + 号。  
        (1). 如果栈内没有任何元素，则直接进行入栈操作  
        (2). 如果栈内有元素，并且栈顶不为‘(’，则将栈内元素取出加入到存储结果的字符串中，最后将该操作符入栈。如果遇到’(’，则表明没有遇到‘)’ 运算优先级高于其他，则将当前操作符直接入栈。
    2.  如果为 ’)’ 则将栈顶元素出栈，直至遇到’(’，并将出栈元素进行存储。
    3.  如果为 \* / 号，则将该元素直接入栈。

下图为运算顺序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

## 2. 利用逆波兰表达式进行计算 ##

### 1). 基本思路 ###

同样将表达式分为两部分，运算符与操作数。不同的是这次将操作数进行入栈。如果遇到了操作符，则从栈顶取出两元素进行运算，并将运算结果继续入栈，反复上述操作，直至运算完成。此过程较为简单，就不再画图阐述，具体实现看下列代码。

# 三. 代码实现 #

## 1.将中缀表达式转换为逆波兰表达式 ##

// 将中缀表达式转换为后缀表达式，表达式元素以空格分隔
    string Infix2SuffixExperisson(sqStack*& sq, string str)
    { 
    	char ch;
    	string dst;
    
    	for (int i = 0; i < str.length(); i++)
    	{ 
    		// 处理连续出现的数字 如果是连续数字 则不加空格进行分隔 eg 10 100 1
    		while ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
    		{ 
    			dst += str[i++];
    
    			if ((str[i] < '0' || str[i] > '9') && str[i] != '.')
    			{ 
    				dst += " ";
    			}
    		}
    
    		if (')' == str[i])
    		{ 
    			StackPop(sq, ch);
    			while (ch != '(')
    			{ 
    				dst += ch;
    				dst += " ";
    
    				StackPop(sq, ch);
    			}
    		}
    		// 当插入 + - 时 需要判断当前是否为空栈 如果是空栈则直接将元素入栈
    		// 在此分支中 对运算符的优先级进行了判断
    		else if (str[i] == '+' || str[i] == '-')
    		{ 
    			// 如果栈内无数据 则将 + - 直接入栈
    			if (!StackLen(sq))
    			{ 
    				StackPush(sq, str[i]);
    			}
    			// 如果不是空栈 则取出栈的当前元素判断是否是 '(' 如果不是 则一定是 '*' 或 '/' 则将该符号从栈内元素取出 进行输出(根据（*优先级进行取出)
    			// 如果是 '(' 则代表一定有对应的另半边
    			else
    			{ 
    				// 后缀表达式 利用计算机的思维进行运算 
    				// * / 优先级比较高，所以要先将* / 进行运算， 如果遇到 + 入栈，则要将栈中所有运算符取出
    				do
    				{ 
    					StackPop(sq, ch);
    
    					if (ch == '(')
    					{ 
    						StackPush(sq, ch);
    					}
    					else
    					{ 
    						dst += ch;
    						dst += " ";
    					}
    				} while (StackLen(sq) && ch != '(');
    
    				StackPush(sq, str[i]);
    			}
    		}
    		else if (str[i] == '*' || str[i] == '/' || str[i] == '(')
    		{ 
    			StackPush(sq, str[i]);
    		}
    		else if (str[i] == '#')
    		{ 
    			break;
    		}
    		else
    		{ 
    			if (i >= str.length())
    			{ 
    				break;
    			}
    			else
    			{ 
    				cout << "数据有误" << endl;
    			}
    		}
    	}
    
    	// 取出栈内剩余的运算符
    	while (StackLen(sq))
    	{ 
    		StackPop(sq, ch);
    
    		dst += ch;
    		dst += " ";
    	}
    
    	return dst;
    }

## 2. 利用逆波兰表达式计算 ##

在以下代码中，为了方便运算，对入栈、出栈函数进行了重载。在参数列表中加入了一项double类型的参数。

// 利用逆波兰表达式进行计算
    double ReversePolishCal(sqStack*& sq, string suffix)
    { 
    	char ch;
    	int j = 0;
    	char str[MAXBUFFER];
    	double num1, num2;
    
    	for(int i = 0; i < suffix.length() - 1; i++)
    	{ 
    		// 处理数字信息， 在字符串型 转换为 双精度
    		while (isdigit(suffix[i]) || suffix[i] == '.')  // 过滤数字
    		{ 
    			str[j++] = suffix[i++];
    			str[j] = '\0';
    
    			if (j >= MAXBUFFER)
    			{ 
    				cout << "数据过大";
    				return -1;
    			}
    
    			if (suffix[i] == ' ')
    			{ 
    				num1 = atof(str);
    				StackPush(sq, num1);
    				j = 0;
    				break;
    			}
    		}
    
    		switch (suffix[i])
    		{ 
    		case '+':
    			StackPop(sq, num1);
    			StackPop(sq, num2);
    			StackPush(sq, num1 + num2);
    			break;
    
    		case '-':
    			StackPop(sq, num1);
    			StackPop(sq, num2);
    			StackPush(sq, num2 - num1);
    			break;
    
    		case '*':
    			StackPop(sq, num1);
    			StackPop(sq, num2);
    			StackPush(sq, num2 * num1);
    			break;
    
    		case '/':
    			StackPop(sq, num1);
    			StackPop(sq, num2);
    			if (num1 != 0)
    			{ 
    				StackPush(sq, num2 / num1);
    			}
    			else
    			{ 
    				cout << "error div = 0" << endl;
    				return -1;
    			}
    
    			break;
    		}
    	}
    
    	// 栈顶存放数据为计算结果
    	StackPop(sq, num1);
    
    	return num1;
    }

[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/115415308
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/d10c45a2598043be8b5366878d55f618.png