NOIP 2005 等价表达式 四则运算

这题就是一个比较经典的四则运算表达式求值

由于只有一个未知数a，所以我们可以选择找几个数带入a 中，然后求值，看与原式子是否相同

中间可能会爆long long ，不过按理来说爆完之后等价的表达式的值还是相同的。

求四则运算的过程也是相当经典的栈的应用了

用两个栈，一个存操作，一个存数

然后符号之间有个优先级别的问题。这时候要分栈内和栈外两种来算 详见我手写了个表

#include <iostream>#include <cstdio>#include <cstring>#include <ctime>#include <cstdlib>#include <stack>#include <cmath>#define eps 1e-6using 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("\n");    return 0;}