逆波兰表达式（STL-栈stack实现）

阳光穿透心脏的1/2处 2022-05-27 08:15 226阅读 0赞

# **一、普及逆波兰表达式** #

## **逆波兰表达式：后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个对象之间，这是中缀表达式，而逆波兰表达式是每一运算符都置于其运算对象之后，所以称为后缀表达式。** ##

**举例：中缀（正常）：8\*4+1**

**后缀：8 4 \* 1 +**

# **暂停！翻下老本** #

##  **1)关于栈：** ##

**暂时博客里写了一篇对STL——Stack的介绍，传送门：[点击打开链接][Link 1]**

##  **2）关于字符串实现计算：** ##

**年前写了一篇处理字符串运算指令（比如：5\*6/6-5+8），涉及运算优先还有就是 atoi和atof 应用，数字，字符没有空格间隔，比较有趣，传送门：[点击打开链接][Link 2]**

# **二、算法** #

**输入你要计算的逆波兰表达式，然后以此读取判断，如果是数字则将其压栈，如果读取到‘+’，‘-’，‘\*’，‘/’，其中的一个，将之前压栈的数据出栈然后进行对用的运算操作，再将其压栈。然后继续向后读取重复之前的判断操作。**

**比如 （8+5）\*2 写成逆波兰表达式就是 8 5 + 2 \* ps：一般题目都是每个字符之间都有空格**

**遇数入栈 1）入栈8，剩余----------- 5 + 2 \***

**2）入栈5，剩余 ------------ + 2 \***

**3）遇 ‘+’ ----------------- 1.出栈之前的 5 8**

**2.运算 8 + 5**

**3.入栈新结果 13；**

**4）入栈2，剩余-------------- \***

**5）遇‘\*’ ---------------------1.出栈2，13**

**2.计算 13 \* 2**

**3.入栈新结果 26**

**6）出栈（肯定只有一个数，因为每逢两个数就会有一次运算）**

# **三、代码实现** #

#include<iostream>	
    #include<stack>
    #define MaxSize 100
    #define Pow 10
    using namespace std;
    int main()
    {
    	int Text_Time;
    	char Reverse_Polish_Notation[MaxSize];
    	cin >> Text_Time;           //输入测试次数
    	getchar();    //消除空格
    	while (Text_Time--)
    	{
    		stack<int> Waiting_Cal_Num;
    		int Num_Bit = 0;      //记录需要入栈的数的位数
    		int Cal_Num = 0;      //入栈的数
    		int i=0;
    		cin.getline(Reverse_Polish_Notation, MaxSize);
    		while (Reverse_Polish_Notation[i]!='#')
    		{
    			if (Reverse_Polish_Notation[i] <= '9'&&Reverse_Polish_Notation[i] >= '0')    //该位是数字
    			{
    				Num_Bit++;                        //记录位数加一
    				Cal_Num = Cal_Num * Pow + (Reverse_Polish_Notation[i] - '0');    //按进制计算整个数的格式，pow是进制
    			}
    			if (Reverse_Polish_Notation[i + 1] == ' '&&Num_Bit)       //整个数读完的情况： 1）下一位是空格 2）Num——Bit不为0，一个计算的数至少是个位
    			{
    				i - Num_Bit >= 0 && Reverse_Polish_Notation[i - Num_Bit] == '-' ? Cal_Num *= -1 : Cal_Num;    //判定读入的是否是负数，是的话转负
    				Waiting_Cal_Num.push(Cal_Num);     //入栈这个数
    				cout << "Cal_Num= " << Cal_Num << endl;   //测试读入是否正确
    				Num_Bit = Cal_Num = 0;              //成功入栈，重新读取下一个数
    			}
    
    			if (Reverse_Polish_Notation[i] == '-'&&Reverse_Polish_Notation[i + 1] == ' ')    //四个if判定计算
    			{
    				int A = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				int B = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				Waiting_Cal_Num.push(B - A);    //取出两个进行运算的数，再重新入栈结果
    			}
    			if (Reverse_Polish_Notation[i] == '+'&&Reverse_Polish_Notation[i + 1] == ' ')
    			{
    				int A = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				int B = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				Waiting_Cal_Num.push(A + B);
    			}
    			if (Reverse_Polish_Notation[i] == '/'&&Reverse_Polish_Notation[i + 1] == ' ')
    			{
    				int A = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				int B = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				Waiting_Cal_Num.push(B / A);
    			}
    			if (Reverse_Polish_Notation[i] == '*'&&Reverse_Polish_Notation[i + 1] == ' ')
    			{
    				int A = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				int B = Waiting_Cal_Num.top();
    				Waiting_Cal_Num.pop();
    				Waiting_Cal_Num.push(A*B);
    			}
    			i++;    //读取++
    		}
    		int Result = Waiting_Cal_Num.top();
    		cout << Result << endl;    //计算完成整个栈剩下一个数，这个数是计算结果
    	}
    	return 0;
    }

渣男又一次自己折了自己的flag，难过~

[Link 1]: https://blog.csdn.net/szu_crayon/article/details/79907455
[Link 2]: https://blog.csdn.net/szu_crayon/article/details/79084045