WA50 分,求助
查看原帖
WA50 分,求助
52244
Gliese楼主2020/6/7 11:53
#include<bits/stdc++.h>
using namespace std;
char s[1100];
struct node
{
	long long num;
	char opt;
	bool isNaN;
	int lst,nxt;
}rep[1100];
map<char,int> prt;
int n;
//预设置
void preset()
{
	prt['+']=1;
	prt['-']=1;
	prt['*']=2;
	prt['/']=2;
	prt['^']=3;
	prt['(']=4;
	prt[')']=4;
}
//打印
void print()
{
	for(int i=1; i<=n; i=rep[i].nxt)
	{
		if(rep[i].isNaN)
			cout<<rep[i].num<<" ";
		else cout<<rep[i].opt<<" ";
	}
	cout<<endl;
}
//中缀转后缀
void change()
{
	int pos=0;
	char stk[110];
	for(int i=0; i<strlen(s); ++i)
	{
		if(s[i]>='0'&&s[i]<='9')
		{
			rep[++n].isNaN=1;
			rep[n].num=s[i]-'0';
		}
		else
		{
			char tmp=stk[pos];
			if(pos>0&&prt[tmp]>=prt[s[i]]&&tmp!='(')
			{
				do
				{
					if(stk[pos]!='('&&stk[pos]!=')')
					{
						rep[++n].isNaN=0;
						rep[n].opt=stk[pos];
					}
					pos--;
				}while(pos>0&&prt[tmp]>prt[stk[pos]]);
				if(stk[pos]=='(')
					pos--;
			}
			stk[++pos]=s[i];
		}
	}
	while(pos>0)
	{
		if(stk[pos]!='('&&stk[pos]!=')')
		{
			rep[++n].isNaN=0;
			rep[n].opt=stk[pos];
		}
		pos--;
	}
	return ;
}
//计算
long long clt(long long a,long long b,char c)
{
	switch(c)
	{
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		case '/': return a/b;
	}
	long long ans=a;
	for(long long i=2; i<=b; ++i)
	{
		ans*=a;
	}
	return ans;
}
//计算后缀
void calculate()
{
	for(int i=1; i<=n; ++i)
	{
		if(!rep[i].isNaN)
		{
			int lst1=rep[i].lst;
			int lst2=rep[lst1].lst;
			int nxt1=rep[i].nxt;
			rep[lst2].num=clt(rep[lst2].num,rep[lst1].num,rep[i].opt);
			rep[lst2].nxt=nxt1;
			rep[nxt1].lst=lst2;
			print();
		}
	}
}
int main()
{
	preset();
	scanf("%s",s);
	change();
	for(int i=1; i<=n; ++i)
	{
		rep[i].lst=i-1;
		rep[i].nxt=i+1;
	}
	print();
	calculate();
	return 0;
}
2020/6/7 11:53
加载中...