转逆波兰表达式-OpenJudge[等价表达式]

た入场券 2022-05-17 02:05 210阅读 0赞

*  # 转逆波兰表达式-OpenJudge\[等价表达式\] #

--------------------

*  ## 题目链接：[5:等价表达式][5] ##
 *  ## 基础相关： ##

### 逆波兰表达式 ###

题目通过将正常式转化成逆波兰式进行求解，有必要复习逆波兰请自行传送门：[逆波兰表达式][Link 1]

*  ## 思路： ##

最难的就是一般式转逆波兰啦

先搞清楚优先级：***括号* > *\** > *+* = *-***

定义：**一串（New\_Equal），逆波兰式**

**一栈（Signal）暂存运算符（包括括号）**

对输入的一般式从头到尾扫一遍

**①遇到“（ ” ：直接入栈**

**②数字和字母：直接进入逆波兰式**

**③“ ）”：将括号内符号逐个加入逆波兰式并出栈直到遇到“（ ”，将“（ ” 出栈**

**④+ or - ：在入栈新的+ or - 之前，将“（ ” 之前（或直到空栈）的全部运算符加入逆波兰式，然后再入栈新的+ or -**

**⑤ \* ：乘法优先级仅低于括号，所以入栈新的 \* 之前，如果之前存在平级的 \*  ，出栈并加入波兰式，直到栈空或“（ ”**

**My Puzzle Before ：**非空下出栈运算符可以理解，但我一直在想为什么遇到“（ ”也要停止出栈运算符，后来想通了，***括号是最高优先级***，所以括号内的运算式优先运算，如果遇到（1+1）-（1\*1），对应于逆波兰就是 1 1 + 1 1 \* -，每次出栈终止于“（ ”，直到遇到 “ ）”**起到了优先处理括号内表达式的作用**，隔离开了 - 使之置于最后。

*  ## 代码： ##

#include<iostream>	
    #include<stack>	
    #include<string>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    #define MAX_Length 500
    //数据结构与算法Mooc（第三章栈与队列5等价表达式）
    string Change_Equal(char* Initial_Equal)
    {
    	int Len = strlen(Initial_Equal);
    	stack<char> Signal;
    	string New_Equal;
    	for (int i = 0; i < Len; i++)
    	{
    		if (Initial_Equal[i] <= '9'&&Initial_Equal[i] >= '0' || Initial_Equal[i] >= 'a'&&Initial_Equal[i] <= 'z')
    			New_Equal += Initial_Equal[i];
    		else if (Initial_Equal[i] == '(')	//左括号直接入运算符栈
    			Signal.push(Initial_Equal[i]);
    		else if (Initial_Equal[i] == ')')
    		{
    			while (Signal.top()!='(')
    			{
    				New_Equal += Signal.top();		//括号内的运算符进入波兰式
    				Signal.pop();
    			}
    			Signal.pop();
    		}
    		else if (Initial_Equal[i] == '+' || Initial_Equal[i] == '-')
    		{
    			while (!Signal.empty() && Signal.top() != '(')   //入加号减号前把括号内其他运算符加入波兰式
    			{
    				New_Equal += Signal.top();
    				Signal.pop();
    			}
    			Signal.push(Initial_Equal[i]);		//入加号或减号
    		}
    		else if (Initial_Equal[i] == '*')
    		{
    			while (!Signal.empty() && Signal.top() != '('&&Signal.top() == '*')		//等同优先级先进入的乘号加入波兰式
    			{
    				New_Equal += Signal.top();
    				Signal.pop();
    			}
    			Signal.push(Initial_Equal[i]);		//再入乘号
    		}
    		else
    			continue;
    	}
    	while (!Signal.empty())		//符号栈不空需要将剩余符号加入波兰式
    	{
    		New_Equal += Signal.top();
    		Signal.pop();
    	}
    
    	return New_Equal;
    }
    
    
    int Get_Sum(string Equal)
    {
    	int Len = Equal.length();
    	stack<int> Data;
    	for (int i = 0; i < Len; i++)
    	{
    		if (Equal[i] <= 'z'&&Equal[i] >= 'a')
    			Data.push((int)Equal[i]);
    		else if (Equal[i] >= '0'&&Equal[i] <= '9')
    			Data.push((int)Equal[i] - '0');
    		else if (Equal[i] == '*')
    		{
    			int data1 = Data.top();
    			Data.pop();
    			int data2 = Data.top();
    			Data.pop();
    			data1 *= data2;
    			Data.push(data1);
    		}
    		else if (Equal[i] == '+')
    		{
    			int data1 = Data.top();
    			Data.pop();
    			int data2 = Data.top();
    			Data.pop();
    			data2 += data1;
    			Data.push(data2);
    		}
    		else if (Equal[i] == '-')
    		{
    			int data1 = Data.top();
    			Data.pop();
    			int data2 = Data.top();
    			Data.pop();
    			data2 -= data1;
    			Data.push(data2);
    		}
    		else
    			continue;
    	}
    	int Res = Data.top();
    	return Res;
    }
    
    int main()
    {
    	char Equal1[MAX_Length];
    	char Equal2[MAX_Length];
    	int t;
    	cin >> t;
    	getchar();
    	while (t--)
    	{
    		cin.getline(Equal1, MAX_Length);
    		cin.getline(Equal2, MAX_Length);
    		string NewEuqal1 = Change_Equal(Equal1);
    		string NewEqual2 = Change_Equal(Equal2);
    		int Sum1 = Get_Sum(NewEuqal1);
    		int Sum2 = Get_Sum(NewEqual2);
    		
    		if (Sum1 == Sum2)
    			cout << "YES" << endl;
    		else
    			cout << "NO" << endl;
    	}
    	return 0;
    }

[5]: http://dsalgo.openjudge.cn/stackqueue/5/
[Link 1]: https://blog.csdn.net/SZU_Crayon/article/details/79944742