当前位置：首页 > news >正文

hdu 4192(表达式求值)

news 来源：原创 2024/5/5 22:42:47

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

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

代码如下：

 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 }