首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。