Skip to main content

表达式求值

参考资料​

多项式​

#include <bits/stdc++.h>
using namespace std;

using T=long long;
char ch;
struct Poly
{
	vector<T> v;
	Poly(initializer_list<T> a={}):v(a){}
	void maintain(){while(!v.empty()&&v.back()==0)v.pop_back();}
	T &operator[](int u){if(u>=v.size())v.resize(u+1,0);return v[u];}
	Poly operator+(const Poly &rhs) const
	{
		Poly res;
		for(int i=0;i<max(v.size(),rhs.v.size());i++)
		{
			res[i]=v[i]+rhs.v[i];
		}
		res.maintain();
		return res;
	}
	Poly operator-(const Poly &rhs) const
	{
		Poly res;
		for(int i=0;i<max(v.size(),rhs.v.size());i++)
		{
			res[i]=v[i]-rhs.v[i];
		}
		res.maintain();
		return res;
	}
	Poly operator*(const Poly &rhs) const
	{
		Poly res;
		for(int i=0;i<v.size();i++)
		{
			for(int j=0;j<rhs.v.size();j++)
			{
				res[i+j]+=v[i]*rhs.v[j];
			}
		}
		res.maintain();
		return res;
	}
	Poly operator^(const Poly &rhs) const
	{
		if(rhs.v.size()!=1)cout<<"warning"<<'\n';
		T exp=rhs.v[0];
		Poly res({1}),base=*this;
		while(exp)
		{
			if(exp&1)res=res*base;
			base=base*base;
			exp>>=1;
		}
		res.maintain();
		return res;
	}
};
void print(Poly a)
{
	bool tmp=1;
	for(int i=a.v.size()-1;i>=0;i--)
	{
		T num=a[i];
		if(num==0)continue;
		if(num<0)cout<<'-';
		else if(!tmp)cout<<'+';
		if(i==0||abs(num)!=1)cout<<abs(num);
		if(i==1)cout<<ch;
		else if(i>1)cout<<ch<<'^'<<i;
		tmp=0;
	}
	if(tmp)cout<<0;
	cout<<'\n';
}
bool isoption(char f){return f=='+'||f=='-'||f=='*'||f=='^';}
bool isvariable(char f){return f==ch;}
int priority(char f)
{
	switch(f)
	{
		case '(':return 0;
		case ')':return 0;
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '^':return 3;
	}
	return 0;
}
stack<Poly> P;
stack<char> F;
void pop()
{
	char f=F.top();F.pop();
	Poly p=P.top();P.pop();
	Poly q=P.top();P.pop();
	switch(f)
	{
		case '+':P.push(q+p);break;
		case '-':P.push(q-p);break;
		case '*':P.push(q*p);break;
		case '^':P.push(q^p);break;
	}
}
Poly calc(string s)
{
	string t;
	for(int i=0;i<s.size();i++)
	{
		if(isalpha(s[i]))
		{
			if(isalpha(ch))s[i]=ch;
			else ch=s[i];
		}
	}
	for(int i=0;i<s.size();i++)
	{
		if((i==0||s[i-1]=='(')&&s[i]=='-')
		{
			t.push_back('0');
		}
		else if(i>0&&(isdigit(s[i-1])||isvariable(s[i-1]))&&isvariable(s[i]))
		{
			t.push_back('*');
		}
		else if(i>0&&(isdigit(s[i-1])||isvariable(s[i-1])||s[i-1]==')')&&s[i]=='(')
		{
			t.push_back('*');
		}
		t.push_back(s[i]);
	}
	s=t;
	while(!P.empty())P.pop();
	while(!F.empty())F.pop();
	for(int i=0;i<s.size();i++)
	{
		if(isdigit(s[i]))
		{
			T num=s[i]-'0';
			while(isdigit(s[i+1]))
			{
				num=num*10+s[++i]-'0';
			}
			P.push(Poly({num}));
		}
		else if(isvariable(s[i]))
		{
			P.push(Poly({0,1}));
		}
		else if(isoption(s[i]))
		{
			while(!F.empty()&&priority(s[i])<=priority(F.top()))pop();
			F.push(s[i]);
		}
		else if(s[i]=='(')
		{
			F.push(s[i]);
		}
		else if(s[i]==')')
		{
			while(!F.empty()&&F.top()!='(')pop();
			F.pop();
		}
	}
	while(!F.empty())pop();
	return P.top();
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	while(cin>>s)
	{
		Poly ans=calc(s);
		print(ans);
	}
	return 0;
}

例题​

洛谷 P1981 [NOIP 2013 普及组] 表达式求值​

洛谷 P1981 [NOIP 2013 普及组] 表达式求值

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

Code (1)
#include <bits/stdc++.h>
using namespace std;

const int mod=10000;
stack<int> s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int x;
	cin>>x;
	s.push(x);
	char f;
	while(cin>>f>>x)
	{
		if(f=='*')
		{
			int t=s.top();
			s.pop();
			x=x*t%mod;
		}
		s.push(x);
	}
	int ans=0;
	while(!s.empty())
	{
		ans=(ans+s.top())%mod;
		s.pop();
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P1310 [NOIP 2011 普及组] 表达式的值​

洛谷 P1310 [NOIP 2011 普及组] 表达式的值

对于 11 位二进制变量定义两种运算：

运算符运算规则⊕0⊕0=00⊕1=11⊕0=11⊕1=1×0×0=00×1=01×0=01×1=1\begin{array}{|c|c|} \hline \qquad\qquad\quad\textsf{运算符}\qquad\qquad\quad & \qquad\qquad\quad\textsf{运算规则}\qquad\qquad\quad \\ \hline \oplus & \begin{aligned} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 1 \\ \end{aligned} \\ \hline \times & \begin{aligned} 0 \times 0 &= 0 \\ 0 \times 1 &= 0 \\ 1 \times 0 &= 0 \\ 1 \times 1 &= 1 \\ \end{aligned} \\ \hline \end{array}

运算的优先级是：

  1. 先计算括号内的，再计算括号外的。
  2. “×\times”运算优先于“⊕\oplus”运算，即计算表达式时，先计算“×\times”运算，再计算“⊕\oplus”运算。例如：计算表达式 A⊕B×CA\oplus B \times C 时，先计算 B×CB \times C，其结果再与 AA 做“⊕\oplus”运算。

现给定一个未完成的表达式，例如 _+(_∗_)\_+(\_ * \_)，请你在横线处填入数字 00 或者 11，请问有多少种填法可以使得表达式的值为 00。

Code (1)
#include <bits/stdc++.h>
using namespace std;

const int mod=10007;
const int N=100005;
stack<pair<int,int>> s1;
stack<char> s2;
void pop()
{
	auto [x0,x1]=s1.top();s1.pop();
	auto [y0,y1]=s1.top();s1.pop();
	char f=s2.top();s2.pop();
	if(f=='*')s1.push({(x0*y0+x0*y1+x1*y0)%mod,x1*y1%mod});
	else if(f=='+')s1.push({x0*y0%mod,(x0*y1+x1*y0+x1*y1)%mod});
}
int pri(char f)
{
	if(f=='('||f==')')return 0;
	else if(f=='+')return 1;
	else if(f=='*')return 2;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	string s;
	cin>>n>>s;
	string t;
	t.push_back('$');
	for(int i=0;i<n;i++)
	{
		t.push_back(s[i]);
		t.push_back('$');
	}
	n=n*2+1;
	for(int i=0;i<n;i++)
	{
		if(t[i]!='$')continue;
		char l=i>0?t[i-1]:'#',r=i<n-1?t[i+1]:'#';
		if((l=='+'||l=='*'||l =='('||l == '#')&&r=='(')continue;
		if(l ==')'&&(r =='+'||r=='*'||r ==')'||r=='#'))continue;
		t[i]='x';
	}
	s=t;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='x')
		{
			s1.push({1,1});
		}
		else if(s[i]=='+'||s[i]=='*')
		{
			while(!s2.empty()&&pri(s[i])<=pri(s2.top()))pop();
			s2.push(s[i]);
		}
		else if(s[i]=='(')
		{
			s2.push(s[i]);
		}
		else if(s[i]==')')
		{
			while(!s2.empty()&&s2.top()!='(')pop();
			s2.pop();
		}
	}
	while(!s2.empty())pop();
	cout<<s1.top().first<<'\n';
	return 0;
}