HAUT1288 等价交换(大数+表达式求值，河南省多校连萌（七）)

题目:

题目描述

输入

输出

样例输入

3

1+1=2

135+342*292=99999

100000*100000=100000

样例输出

Yes

No

提示

来源

思路：

没什么好说的，一定要注意细节，我debug了好长时间，原来是中缀转后缀的时候出错了。。尴尬

记得注意一下，等式两边都是表达式，而不是样例给的左边是表达式，右边是值。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define M 12357
#define ll long long
using namespace std;
string multi_string_int(string a,int k)
{
	if(k == 0) return "0";
	int len = a.length(),carry = 0;
	reverse(a.begin(),a.end());
	for(int i = 0; i < len; i++)
	{
		int s = (a[i] - '0') * k + carry;
		a[i] = s % 10 + '0';
		carry = s / 10;
	}
	while(carry != 0)
	{
		a = a + (char)(carry % 10 + '0');
		carry /= 10;
	}
	reverse(a.begin(),a.end());
	return a;
}
string add(string a,string b)
{
	string s;
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	int i = 0;
	int m,k = 0;
	while(a[i] && b[i])
	{
		m = a[i] - '0' + b[i] - '0' + k;
		k = m / 10;
		s += (m % 10 + '0');
		i++;
	}
	if(i == a.size())
	{
		while(i != b.size())
		{
			m = k + b[i] - '0';
			k = m / 10;
			s += m % 10 + '0';
			i++;
		}
		if(k) s += k + '0';
	}
	else if(i == b.size())
	{
		while(i != a.size())
		{
			m = k + a[i] - '0';
			k = m / 10;
			s += m % 10 + '0';
			i++;
		}
		if(k) s += k + '0';
	}
	reverse(s.begin(),s.end());
	return s;
}
string multi_string_string(string a,string b)
{
	string ans = "";
	for(int i = a.size() - 1; i >= 0; i--)
	{
		string tmp = multi_string_int(b,a[i] - '0');
		for(int j = 0; j < a.size() - 1 - i; j++)
			tmp += '0';
		ans = add(ans,tmp);
	}
	return ans;
}
string init(string s)//中缀转后缀,传入中缀
{
	string ans="";
	stack<char>s1;//运算符栈
	map<char,int>mp;
	mp['+']=1;
	mp['*']=2;
	for(int i=0; i<s.length(); i++)
	{
		if(isdigit(s[i]))
		{
			while(isdigit(s[i]))
			{
				ans+=s[i];
				i++;
			}
			i--;
			ans+="#";
		}
		else
		{
			if(s1.empty())
			{
				s1.push(s[i]);
			}
			else
			{
				if(mp[s[i]]>=mp[s1.top()])
				{
					s1.push(s[i]);
				}
				else
				{
					while(!s1.empty()&&mp[s[i]]<mp[s1.top()])
					{
						ans+=s1.top();
						s1.pop();
					}
					s1.push(s[i]);
				}
			}
		}
	}
	while(!s1.empty())
	{
		ans+=s1.top();
		s1.pop();
	}
	return ans;
}
string calc(string s)//由后缀求结果
{
	stack<string>s1;//计算表达式
	string num="";
	for(int i=0; i<s.length(); i++)
	{
		if(isdigit(s[i]))
		{
			while(isdigit(s[i]))
			{
				num+=s[i];
				i++;
			}
			s1.push(num);
			num="";
		}
		else if(s[i]=='+')
		{
			string x=s1.top();
			s1.pop();
			string y=s1.top();
			s1.pop();
			string ans=add(x,y);
			if(ans[0]=='0')ans="0";
			s1.push(ans);
		}
		else if(s[i]=='*')
		{
			string x=s1.top();
			s1.pop();
			string y=s1.top();
			s1.pop();
			string ans=multi_string_string(x,y);
			if(ans[0]=='0')ans="0";
			s1.push(ans);
		}
	}
	return s1.top();
}

int main()
{
	int t;
	string str;
	cin>>t;
	while(t--)
	{
		string str1="",str2="";//两个等式
		int flag=1;
		cin>>str;
		for(int i=0; i<str.length(); i++)
		{
			if(flag)
			{
				if(str[i]=='=')
				{
					flag=0;
					continue;
				}
				str1+=str[i];
			}
			else
				str2+=str[i];
		}
		string ans1=calc(init(str1));
		string ans2=calc(init(str2));
		if(ans1==ans2)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}