明明進了中學之後，學到了代數表達式。有一天，他碰到一個很麻煩的選擇題。這個題目的題幹中首先給出了一個代數表達式，然後列出了若干選項，每個選項也是一個代數表達式，題目的要求是判斷選項中哪些代數表達式是和題幹中的表達式等價的。
這個題目手算很麻煩，因爲明明對計算機編程很感興趣，所以他想是不是可以用計算機來解決這個問題。假設你是明明，能完成這個任務嗎？
這個選擇題中的每個表達式都滿足下面的性質：
1． 表達式只可能包含一個變量‘a’。
2． 表達式中出現的數都是正整數，而且都小於10000。
3． 表達式中可以包括四種運算‘+’（加），‘-’（減），‘*’（乘），‘^’（乘冪），以及小括號‘(’，‘)’。小括號的優先級最高，其次是‘^’，然 後是‘*’，最後是‘+’和‘-’。‘+’和‘-’的優先級是相同的。相同優先級的運算從左到右進行。（注意：運算符‘+’，‘-’，‘*’，‘^’以及 小括號‘(’，‘)’都是英文字符）
4． 冪指數只可能是1到10之間的正整數（包括1和10）。
5． 表達式內部，頭部或者尾部都可能有一些多餘的空格。
下面是一些合理的表達式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
【輸入文件】
輸入文件 的第一行給出的是題幹中的表達式。第二行是一個整數 n （ 2 <= n <= 26 ），表示選項的個數。後面 n 行，每行包括一個選項中的表達式。這 n 個選項的標號分別是 A ， B ， C ， D ……
輸入中的表達式的長度都不超過 50 個字符，而且保證選項中總有表達式和題幹中的表達式是等價的。
【輸出文件】
輸出文件 包括一行，這一行包括一系列選項的標號，表示哪些選項是和題幹中的表達式等價的。選項的標號按照字母順序排列，而且之間沒有空格。
【輸入樣例】
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
【輸出樣例】
AC
【數據規模】
對於30%的數據，表達式中只可能出現兩種運算符‘+’和‘-’；
對於其它的數據，四種運算符‘+’，‘-’，‘*’，‘^’在表達式中都可能出現。
對於全部的數據，表達式中都可能出現小括號‘(’和‘)’。
【試題分析】
以下部分題解參考了BYVoid大牛的博客：
這道題很顯然不是讓寫多項式展開的程序的。只需要代入幾次，判斷與題幹中表達式等價的表達式即可。
注意：不能只代入一個簡單的數如1，2等，因爲你把測試數據中給的表達式聯立方程組，就會發現1、2是常見的解。而且代入的數不能太大，因爲太大會導致數據超出long long 的範圍～我直到試到23時才發現能過所有的數據。
所以，多代入幾次，避免值同而質不同的情況，
是考場中比較明智的選擇。
注意，只有加法、減法、乘法、乘冪四種運算，沒有除法！這意味着計算表達式的時候不用考慮出現小數的問題，數據類型要用8字節整型，即long long。
本題需要用到的一個函數：
乘方計算函數（不能用pow函數）
long long power(long long a,long long b)
{
long long k=1;
for(int i=0;i<b;i++)
k*=a;
return k;
}
我們可以定義
long long num[50],//數字堆棧
op[50]; //運算符號棧
那麼，我們可以把用於操作棧頂元素的程序寫成函數，方便調用：
void cul(int p,int op)
{
if(op==0) num[p-1]=num[p-1]+num[p];
if(op==1) num[p-1]=num[p-1]-num[p];
if(op==2) num[p-1]=num[p-1]*num[p];
if(op==5) num[p-1]=power( num[p-1],num[p] );
}
然後整個程序的核心部分就剩下處理運算符的優先級了。
string str;//str是儲存表達式的字符串
int op_nxt,//下一個即將入棧操作符
len=str.length(),
p=-1,q=-1; //數字棧、符號棧的指針
long long num_nxt=0;//下一個即將入棧的數字
for (i=0, i<len;i++)
{
if(str[i]是未知數a) 把對a測試的數據入數棧;
if(str[i]是數字) num_nxt*10+(str[i]-'0')
if(str[i]是運算符)
{
得到str[i]的編號op_nxt;
if(op_nxt是左括號) 直接入棧;
if(op_nxt是右括號) 依次將棧頂元素出棧，直到op棧棧頂元素是'('爲止;
if(op_nxt<=op[q]) 開始從右往左計算表達式，直到 op[q]>op_nxt爲止，並將op_nxt入棧;
}
}
//最後，清空堆棧（在大循環外面）
if(num_nxt!=0)
{
將num_nxt入棧;
}
while(q>=0)
{
從右往左計算表達式的值;
q--;
}
return num[0]
【完整代碼】
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long check=23,
result_t,
final;
long long num[50],//數字棧
op[50]; //運算符號棧
long long power(long long a,long long b)
{
long long k=1;
for(int i=0;i<b;i++)
k*=a;
return k;
}
//操作棧頂的兩個元素
void cul(int p,int op)
{
if(op==0) num[p-1]=num[p-1]+num[p];
if(op==1) num[p-1]=num[p-1]-num[p];
if(op==2) num[p-1]=num[p-1]*num[p];
if(op==5) num[p-1]=power( num[p-1],num[p] );
}
long long result(string str)
{
int op_nxt,//下一個即將入棧操作符
len=str.length(),
p=-1,q=-1; //數字棧、符號棧的指針
long long num_nxt=0;//下一個即將入棧的數字
for(int i=0;i<len;i++)
{
if(str[i]=='a')
{
num[++p]=check;
}
else if(str[i]>='0' && str[i]<='9')
{
num_nxt=num_nxt*10+(str[i]-'0');
}
else if(str[i]!=' ')
{
if( num_nxt!=0)
{
num[++p]=num_nxt;
num_nxt=0;
}
if(str[i]=='+') op_nxt=0;
if(str[i]=='-') op_nxt=1;
if(str[i]=='*') op_nxt=2;
if(str[i]=='^') op_nxt= 5;
if(str[i]=='(') op_nxt=6;
if(str[i]==')') op_nxt=7;
//如果有括號，則括號的優先級最高
if(op_nxt==6)
{
op[++q]=op_nxt;
}
else if(op_nxt==7)
{
while(q>=0 && op[q--]!=6)
{ //從上一個與該右括號匹配的左括號開始處理括號內的表達式
cul(p--,op[q+1]);
}
}
else
{ //從棧頂開始，把優先級高的運算符出棧
while( q >= 0 && op[q] <= 5 && op[q]/2>=op_nxt/2)
{
cul(p--,op[q--]);
}
op[++q]=op_nxt;
}
}
}
//在最後清空堆棧
if(num_nxt!=0)
{
num[++p]=num_nxt;
num_nxt=0;
}
while(q>=0)
{
cul(p--,op[q--]);
}
return num[0];
}
int main()
{
freopen("equal.in","r",stdin);
freopen("equal.out","w",stdout);
string str1,str2;
int n;
final=0;
getline(cin,str1);
cin>>n;
getline(cin,str2);//過濾換行符
while(n--)
{
bool flag=true;
getline(cin,str2);
for (int i=10;i<=20;i++)
{
check=i;
if (result(str1)!=result(str2))
{
flag=false;
break;
}
}
if (flag) cout<<(char)('A'+final);
final++;
}
cout<<endl;
return 0;
}
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.023 s | 275 KB | 0 |
| 2 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 3 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 4 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 5 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 6 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 7 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 8 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 9 | 正确 | 10 | 0.001 s | 275 KB | 0 |
| 10 | 正确 | 10 | 0.001 s | 275 KB | 0 |
运行时间 0.031 s
平均内存使用 275 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
沒有留言:
張貼留言