玄5关,列文虎克
查看原帖
玄5关,列文虎克
533402
liusihe楼主2025/7/23 15:33
#include <bits/stdc++.h>
using namespace std;
string s1;
string s[20001],str1[20001];
long long str2[20001];
int top1,top2,a1;
map<char,int> ff;
long long mypow(long long a,long long b)
{
	long long r=1, base=a;
	while(b!=0)
	{
		if(b&1ll)
		{
			r*=base;
		}
		base*=base;
		b>>=1ll;
	}
	return r;
}
int main() {
//	freopen("rpn.in","r",stdin);
//	freopen("rpn.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>s1;
	ff['(']=ff[')']=5;
	ff['^']=4;
	ff['*']=ff['/']=3;
	ff['+']=ff['-']=2;
	string num="";
	int suml=0;
	bool fu=false;
	int sumn=0,sumf=0;
	for (int i=0;i<s1.length();i++)
	{
		if (s1[i]>='0' && s1[i]<='9')
		{
			if ((s1[i-1]>='0' && s1[i-1]<='9') && i!=0)
			{
				num+=s1[i];
			}
			else
			{
				num=s1[i];
			}
			if (!(s1[i+1]>='0' && s1[i+1]<='9'))
			{
				sumn++;
				if (fu)
				{
					num+='-';
				}
				fu=false;
				s[++a1]=num;
			}
		}
		else
		{
			if (s1[i]=='(')
			{
				suml++;
				str1[++top1]=s1[i];
			}
			else if (s1[i]==')')
			{
				if (suml==0)
				{
					continue;
				}
				while (top1>0 && str1[top1][0]!='(')
				{
					s[++a1]=str1[top1--];
				}
				top1--;
				suml--;
			}
			else if (ff[s1[i]]>ff[str1[top1][0]] || str1[top1][0]=='(' || top1==0)
			{
				if (s1[i]=='-' && s1[i+1]>='0' && s1[i+1]<='9' && (sumn!=sumf+1 || i==0))
				{
					fu=true;
					continue;
				}
				sumf++;
				str1[++top1]=s1[i];
			}
			else
			{
				if (s1[i]=='-' && s1[i+1]>='0' && s1[i+1]<='9' && (sumn!=sumf+1 || i==0))
				{
					fu=true;
					continue;
				}
				sumf++;
				while (str1[top1][0]!='(' && ff[s1[i]]<=ff[str1[top1][0]])
				{
					s[++a1]=str1[top1--];
				}
				str1[++top1]=s1[i];
			}
		}
	}
	while (top1>0)
	{
		while (str1[top1][0]=='(')
		{
			top1--;
		}
		s[++a1]=str1[top1--];
	}
	for (int i=1;i<=a1;i++)
	{
		if (s[i][0]>='0' && s[i][0]<='9')
		{
			int num1=0;
			int ii=0;
			if (s[i][s[i].length()-1]=='-')
			{
				ii=1;
			}
			for (int j=0;j<s[i].length()-ii;j++)
			{
				num1*=10;
				num1+=s[i][j]-'0';
			}
			if (ii==1)
			{
				num1=-num1;
			}
			str2[++top2]=num1;
			
		}
		else
		{
			long long a,b;
			a=str2[top2--];
			b=str2[top2--];
			switch(s[i][0])
			{
				case '+':str2[++top2]=b+a;break;
				case '-':str2[++top2]=b-a;break;
				case '*':str2[++top2]=a*b;break;
				case '/':str2[++top2]=b/a;break;
				case '^':str2[++top2]=mypow(b,a);break;
			}
		}
	}
	cout<<str2[top2];
	return 0;
}
/*
-1+(-1+7)*5
*/

60pts 前两个 wa了。

2025/7/23 15:33
加载中...