NOIP 2005等価式四則演算
4015 ワード
この問題は古典的な4つの演算式を比較して値を求めます
未知数aが1つしかないので、いくつかの数を探してaに持ち込んで、元の式と同じかどうかを評価することができます.
途中でlong longが爆発する可能性がありますが、爆発後の等価な式の値は同じです.
四則演算を求める過程もかなり古典的なスタックの応用である.
2つのスタック、1つのストレージ操作、1つのストレージ数で
次に、シンボルの間に優先度の問題があります.この時はスタック内とスタック外の2種類に分けて計算しなければならない.詳しくは私が手書きで表を書いたのを参照してください.
未知数aが1つしかないので、いくつかの数を探してaに持ち込んで、元の式と同じかどうかを評価することができます.
途中でlong longが爆発する可能性がありますが、爆発後の等価な式の値は同じです.
四則演算を求める過程もかなり古典的なスタックの応用である.
2つのスタック、1つのストレージ操作、1つのストレージ数で
次に、シンボルの間に優先度の問題があります.この時はスタック内とスタック外の2種類に分けて計算しなければならない.詳しくは私が手書きで表を書いたのを参照してください.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <cmath>
#define eps 1e-6
using namespace std;
char str1[55], str2[55];
char s1[55], s2[55];
int nei[333], wai[333];
int len;
long long tet[10] = {11, 15, 18, 25, 29, 30, 36, 50, 55, 70};
stack<char>optr;
stack<long long>opnd;
bool flag;
long long calculate(long long x, long long y, char c)
{
switch(c)
{
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '^':
long long tmp = 1;
for(int i = 0; i < y; i++) tmp *= x;
return tmp;
}
}
char cmp(char a, char b)
{
if(nei[a] > wai[b]) return '>';
else if(nei[a] == wai[b]) return '=';
return '<';
}
long long gao(char *s, long long t)
{
int i = 0;
long long num;
while(s[i] != '#' || optr.top() != '#')
{
num = 0;
if(!flag) return -1;
if(s[i] >= '0' && s[i] <= '9')
{
while(s[i] >= '0' && s[i] <= '9')
{
num *= 10;
num += s[i] - '0';
i++;
}
opnd.push(num);
}
else if(s[i] == 'a')
{
num = t;
opnd.push(num);
i++;
}
else
{
switch(cmp(optr.top(), s[i]))
{
case '<' : optr.push(s[i]); i++; break;
case '=' : optr.pop(); i++; break;
case '>' :
if(opnd.empty())
{
flag = false;
return -1;
}
long long ta = opnd.top();
opnd.pop();
if(opnd.empty())
{
flag = false;
return -1;
}
long long tb = opnd.top();
opnd.pop();
opnd.push(calculate(tb, ta, optr.top()));
optr.pop();
break;
}
}
}
return opnd.top();
}
void init()
{
while(!opnd.empty()) opnd.pop();
while(!optr.empty()) optr.pop();
optr.push('#');
}
int main()
{
nei['+'] = 2; wai['+'] = 1;
nei['-'] = 2; wai['-'] = 1;
nei['*'] = 4; wai['*'] = 3;
nei['^'] = 6; wai['^'] = 5;
nei[')'] = 8; wai[')'] = 0;
nei['('] = 0; wai['('] = 8;
nei['#'] = -1; wai['#'] = -1;
gets(str1);
len = 0;
for(int i = 0; str1[i]; i++)
if(str1[i] != ' ') s1[len++] = str1[i];
s1[len++] = '#';
s1[len] = '\0';
int cas;
scanf("%d", &cas);
getchar();
for(int i = 0; i < cas; i++)
{
gets(str2);
len = 0;
for(int j = 0; str2[j]; j++)
if(str2[j] != ' ') s2[len++] = str2[j];
s2[len++] = '#';
s2[len] = '\0';
flag = 1;
for(int j = 0; j < 10; j++)
{
init();
long long t1 = gao(s1, tet[j]);
init();
long long t2 = gao(s2, tet[j]);
if(t1 != t2)
{
flag = 0;
break;
}
}
if(flag) printf("%c", i + 'A');
}
printf("
");
return 0;
}