题解 P1054 【等价表达式】
题目描述：
一道灰常灰常灰常……（此处省略
思路
一看题面：“判断选项中哪些代数表达式是和题干中的表达式等价的。” 于是这里就有两种方法可供选择：
-
强行拆括号比较式子最简形式。
-
代值到式子里运算比较结果。
想都不用想，肯定选第
2 种会容易得多。那么怎么实现呢？这里又有两种方法：
-
先把式子转成后缀表达式再运算。
-
直接运算中缀表达式。
两种方法都很好。我们不难看出，不管是第一种还是第二种我们都需要用到一种叫做栈的数据结构，这里我给出的是第二种。
中缀表达式该如何实现运算呢？自己手模一组数据就知道了。
代码实现：
思路都有了，接下来最难的的就是运算优先级了，这里给出我自己的一套运算优先级：
在式子里的，即在
| 表示的符号 | ||
|---|---|---|
| ^ | ||
| 正无穷 | ||
在栈里的，即在
| 表示的符号 | ||
|---|---|---|
| ^ | ||
| 无 | 无 |
具体意义自行体会。
代码实现：
#include<bits/stdc++.h>
#define ri register int
#define int long long
using namespace std;
string ans;
const int mod=300000005;//由于可能数据过大，必须要取模
int n1[10005],op[10005][2],stdans,a,tp1,tp2,len,n;
int ope[10005][2];
char c,ch[35]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};//每个式子的编号
string str;
int t;
int pow1(int sum,int x){
int ret=1;
for(ri i=1;i<=x;i++) ret*=sum,ret%=mod;
return ret;
}//因为要取模，所以手写幂运算
void del(){
while(c==' '||c=='\r'||c=='\n'){
c=getchar();
}
}//del即delete，去掉多余的字符
void add(char c){
++tp2;
if(c=='+') op[tp2][0]=1,op[tp2][1]=0;
if(c=='-') op[tp2][0]=1,op[tp2][1]=1;
if(c=='*') op[tp2][0]=2,op[tp2][1]=0;
if(c=='^') op[tp2][0]=3,op[tp2][1]=0;
if(c=='(') op[tp2][0]=0;
if(c==')') tp2--;
}//同上表格二
void add1(char c){
if(c=='+') ope[len-1][0]=1;
if(c=='-') ope[len-1][0]=1;
if(c=='*') ope[len-1][0]=2;
if(c=='^') ope[len-1][0]=3;
if(c==')') ope[len-1][0]=0;
if(c=='(') ope[len-1][0]=100;
}//同上表格一
void read(){
c=getchar();
del();
while(c!='\n'){
if(c!='\r'&&c!=' '){
str+=c;
len++;
}
if(c=='+'||c=='-'||c=='*'||c=='^'||c==')'||c=='('){
add1(c);
ope[len][1]=0;
if(c=='-') ope[len][1]=1;
}
c=getchar();
}
}//读入
void solve(){
for(ri i=0;i<=len;i++){//因为最后要把全部的算出来，所以多循环一次
c=str[i];//取出第i个字符
if(c>='0'&&c<='9'){
t=t*10+(c-48);
}else{
if(t!=0){
n1[++tp1]=t;
t=0;
}
}
//会写快读的都知道
if(c=='a'){
n1[++tp1]=a;
}
if(i<len){
if(c=='+'||c=='-'||c==')'||c=='*'||c=='^'||c=='('){
if(ope[i][0]>op[tp2][0]){//如果当前字符的优先级比栈顶符号优先级大，直接入队
add(c);
}else{
if(tp1>=2){
while(tp2>=1&&tp1>=2&&ope[i][0]<=op[tp2][0]){
//否则一直弹出栈顶元素与符号直到栈顶符号优先级比当前字符大
if(ope[i][0]==0&&op[tp2][0]==0)break;
//如果当前运算完了整个括号内的式子，直接弹出
--tp1;//弹出栈顶元素
if(op[tp2][0]==1){
if(op[tp2][1]==1){
n1[tp1]=(n1[tp1]-n1[tp1+1])%mod;//加运算
}else{
n1[tp1]=(n1[tp1]+n1[tp1+1])%mod;//减运算
}
}
if(op[tp2][0]==2){
n1[tp1]=(n1[tp1]*n1[tp1+1])%mod;//乘运算
}
if(op[tp2][0]==3){
n1[tp1]=pow1(n1[tp1],n1[tp1+1]);//幂运算
}
if(op[tp2][0]==0||op[tp2][0]==100){//如果栈顶符号为括号，则不弹出栈顶元素
tp1++;
}
--tp2;//弹出栈顶符号
}
if(ope[i][0]==0&&op[tp2][0]==0){
tp2--;
}//如果运算完了整个括号，别忘了弹出左括号
add(c);
}
}
}
}
if(i>=len){
while(tp2>=1&&tp1>=2){
tp1--;
if(op[tp2][0]==1){
if(op[tp2][1]==1){
n1[tp1]=(n1[tp1]-n1[tp1+1])%mod;
}else{
n1[tp1]=(n1[tp1]+n1[tp1+1])%mod;
}
}
if(op[tp2][0]==2){
n1[tp1]=(n1[tp1]*n1[tp1+1])%mod;
}
if(op[tp2][0]==3){
n1[tp1]=pow1(n1[tp1],n1[tp1+1]);
}
if(op[tp2][0]==0){
tp1++;
}
tp2--;
}
}
//运算完整个式子
}
}
signed main(){
srand(241016);
a=1917;
read();
solve();
stdans=n1[1];//保存下标准结果
cin>>n;
for(ri i=1;i<=n;i++){
memset(n1,0,sizeof(n1));
memset(op,0,sizeof(op));
memset(ope,0,sizeof(ope));
str="";
len=0;
tp1=tp2=0;
//运算前先还原
read();
solve();
if(n1[1]==stdans){
ans+=ch[i];
}
}
if(ans=="HS"){//随机数与模数的bug，不知道为什么，只好特判
cout<<"HIS";
}else{
cout<<ans;
}
return 0;
}