首页 > 代码库 > hdu 4192(表达式求值)

hdu 4192(表达式求值)

题意:给一个表达式当中有一些变量,然后告诉你一些数字你可以任意排列,问能不能求出要求的结果。

思路:由于变量数目较小所以直接全排列枚举即可,然后用栈处理表达式。

代码如下:

 1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-06-28 21:50 5  * Filename     : hdu_4192.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include <iostream>10 #include <cstdio>11 #include <cstring>12 #include <cstdlib>13 #include <cmath>14 #include <algorithm>15 #include <queue>16 #include <stack>17 #include <vector>18 #include <set>19 #include <map>20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair<int, int> pii;26 typedef pair<unsigned int,unsigned int> puu;27 typedef pair<int, double> pid;28 typedef pair<ll, int> pli;29 typedef pair<int, ll> pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 10100;34 int n, res, a, num[LEN], len;35 char str[LEN];36 map<char, int> mp;37 38 struct P{39     int x;40     char c;41     P(){}42     P(int _x){x = _x;}43     P(char _c){c = _c;}44 };45 46 int top;47 int ch(char c){48     if(!mp.count(c)) mp[c] = top++;49     return mp[c];50 }51 52 bool calc(){53     stack<P> s;54     for(int i=0; i<len; i++){55         if(str[i] == () continue;56         else if(str[i] == + || str[i] == - || str[i] == *){57             s.push(P(str[i]));58         }else if(str[i] >= a && str[i] <= z){59             s.push(P(num[ch(str[i])]));60         }else if(str[i] == )){61             P a = s.top();s.pop();62             P op = s.top();s.pop();63             P b = s.top();s.pop();64             switch(op.c){65                 case +: b.x+=a.x;break;66                 case -: b.x-=a.x;break;67                 case *: b.x*=a.x;break;68             }69             s.push(b);70         }71     }72     return s.top().x == res;73 }74 75 bool solve(){76     sort(num, num + n);77     do{78         if(calc()) return true;79     }while(next_permutation(num, num + n));80     return false;81 }82 83 int main()84 {85 //    freopen("in.txt", "r", stdin);86 87     while(scanf("%d", &n)!=EOF){88         mp.clear();top = 0;89         for(int i=0; i<n; i++)90             scanf("%d", &num[i]);91         scanf("%d", &res);92         if(!n && !res) break;93         scanf("%s", &str);94         len = strlen(str);95         if(solve()) puts("YES");96         else puts("NO");97     }98     return 0;99 }
View Code