60分分治递归求调
查看原帖
60分分治递归求调
1426730
__kevin_楼主2025/1/20 09:05

前两个点TLETLE,后三个点ACAC

#include <bits/stdc++.h>
using namespace std;
// 将int转换为string 
string itos(int i)
{
	string s="";
	while(i>0)
	{
		s=char(i%10+'0')+s;
		i/=10;
	}
	return s;
}
// 将string转换为int 
int zstoi(string s)
{
	int res=0;
	for(int i=0;i<s.size();i++)
	{
		res*=10;
		res+=s[i]-'0';
	}
	return res;
}
// 判断字符串是否由数字组成 
bool zsisi(string s)
{
	for(int i=0;i<s.size();i++)
	{
		if(!(s[i]>='0'&&s[i]<='9'))
		{
			return false;
		}
	}
	return true;
}
// 表达式求值 
int expression(string s)
{
	int res=0;
	if(zsisi(s))
	{
		return zstoi(s);
	}
	else
	{
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='(')
			{
				int de=1;
				for(int j=i+1;j<s.size();j++)
				{
					if(s[j]==')')
					{
						de--;
						if(de<=0)
						{
							res=expression(s.substr(0,i)+itos(expression(s.substr(i+1,j-i-1)))+s.substr(j+1,s.size()));
							return res;
						}
					}
					else if(s[j]=='(')
					{
						de++;
					}
				}
			}
		}
		for(int i=s.size()-1;i>=0;i--)
		{
			if(s[i]=='+')
			{
				res+=expression(s.substr(0,i))+expression(s.substr(i+1,s.size()));
//				cout << s << "=" << res << endl;
				return res;
			}
			else if(s[i]=='-')
			{
				res+=expression(s.substr(0,i))-expression(s.substr(i+1,s.size()));
//				cout << s << "=" << res << endl;
				return res;
			}
		}
		for(int i=s.size()-1;i>=0;i--)
		{
			if(s[i]=='*')
			{
				res+=expression(s.substr(0,i))*expression(s.substr(i+1,s.size()));
//				cout << s << "=" << res << endl;
				return res;
			}
			else if(s[i]=='/')
			{
				res+=expression(s.substr(0,i))/expression(s.substr(i+1,s.size()));
//				cout << s << "=" << res << endl;
				return res;
			}
			else if(s[i]=='^')
			{
				res+=pow(expression(s.substr(0,i)),expression(s.substr(i+1,s.size())));
//				cout << s << "=" << res << endl;
				return res;
			}
			else if(s[i]=='%')
			{
				res+=expression(s.substr(0,i))%expression(s.substr(i+1,s.size()));
//				cout << s << "=" << res << endl;
				return res;
			}
			else if(s[i]=='(')
			{
				int de=1;
				while(true)
				{
					if(s[i]==')')
					{
						if((--de)<=0)
						{
							break;
						}
					}
					else if(s[i]=='(')
					{
						de++;
					}
				}
			}
		}
	}
}
int main()
{
    string s;
    cin >> s;
    cout << expression(s);
    return 0;
}
2025/1/20 09:05
加载中...