http://acm.pku.edu.cn/JudgeOnline/problem?id=1460
没啥好说的，就是赤裸裸的表达式求值。先2^n枚举运算符，复杂度是O(2^n * len)，len是表达式的长度。一开始以为是只有一个问号，结果wa了一次才发现是最多有10个问号……这次想练代码，所以没用STL，但是又有点偷懒，所以就复制粘贴了一些代码，而没写成函数……
1 #include <cstdio>
2
3 const int MAX_LEN = 110;
4 const int MAX_MARK = 11;
5 const char REPLACE[] = {'+', '-', '*', '/'};
6
7 template <class T>
8 class Stack {
9
10 private:
11 T base[MAX_LEN];
12 int tail;
13
14 public:
15 Stack() : tail(0) {}
16 void push(T x) {
17 base[tail++] = x;
18 }
19 T top() {
20 return base[tail - 1];
21 }
22 void pop() {
23 --tail;
24 }
25 bool empty() {
26 return !tail;
27 }
28
29 };
30
31 int mk[MAX_MARK];
32 char st1[MAX_LEN], st2[MAX_LEN * 2];
33 int cas, ret, marks;
34
35 int main() {
36 for (scanf("%d", &cas); cas; --cas) {
37 scanf("%s", st1);
38 scanf("%d", &ret);
39 marks = 0;
40 for (int i = 0; st1[i]; ++i)
41 if (st1[i] == '?') mk[marks++] = i;
42 bool flag = 0;
43 for (int k = 0; k < 1 << 2 * marks; ++k) {
44 for (int i = 0; i < marks; ++i) {
45 st1[mk[i]] = REPLACE[((k & 1 << i * 2) >= 1) * 2 + ((k & 1 << i * 2 + 1) >= 1)];
46 }
47 Stack <char> op;
48 int len = 0;
49 for (int i = 0; st1[i]; ++i) {
50 if (st1[i] >= '0' && st1[i] <= '9') {
51 while (st1[i] >= '0' && st1[i] <= '9') st2[len++] = st1[i++];
52 st2[len++] = ' ';
53 --i;
54 } else {
55 switch (st1[i]) {
56 case '+':
57 case '-':
58 while (!op.empty() && op.top() != '(') {
59 st2[len++] = op.top();
60 op.pop();
61 }
62 op.push(st1[i]);
63 break;
64 case '*':
65 case '/':
66 while (!op.empty() && (op.top() == '*' || op.top() == '/')) {
67 st2[len++] = op.top();
68 op.pop();
69 }
70 op.push(st1[i]);
71 break;
72 case '(':
73 op.push(st1[i]);
74 break;
75 case ')':
76 while (op.top() != '(') {
77 st2[len++] = op.top();
78 op.pop();
79 }
80 op.pop();
81 break;
82 }
83 }
84 }
85 Stack <int> num;
86 bool ok = 1;
87 for (int i = 0; ok && i < len; ++i) {
88 if (st2[i] >= '0' && st2[i] <= '9') {
89 int tmp = 0;
90 while (st2[i] >= '0' && st2[i] <= '9') tmp = tmp * 10 + st2[i++] - '0';
91 num.push(tmp);
92 } else {
93 int num1, num2;
94 switch (st2[i]) {
95 case '+':
96 num2 = num.top();
97 num.pop();
98 num1 = num.top();
99 num.pop();
100 num.push(num1 + num2);
101 break;
102 case '-':
103 num2 = num.top();
104 num.pop();
105 num1 = num.top();
106 num.pop();
107 num.push(num1 - num2);
108 break;
109 case '*':
110 num2 = num.top();
111 num.pop();
112 num1 = num.top();
113 num.pop();
114 num.push(num1 * num2);
115 break;
116 case '/':
117 num2 = num.top();
118 if (!num2) {
119 ok = 0;
120 break;
121 }
122 num.pop();
123 num1 = num.top();
124 num.pop();
125 num.push(num1 / num2);
126 break;
127 }
128 }
129 }
130 while (ok && !op.empty()) {
131 int num1, num2;
132 switch (op.top()) {
133 case '+':
134 num2 = num.top();
135 num.pop();
136 num1 = num.top();
137 num.pop();
138 num.push(num1 + num2);
139 break;
140 case '-':
141 num2 = num.top();
142 num.pop();
143 num1 = num.top();
144 num.pop();
145 num.push(num1 - num2);
146 break;
147 case '*':
148 num2 = num.top();
149 num.pop();
150 num1 = num.top();
151 num.pop();
152 num.push(num1 * num2);
153 break;
154 case '/':
155 num2 = num.top();
156 if (!num2) {
157 ok = 0;
158 break;
159 }
160 num.pop();
161 num1 = num.top();
162 num.pop();
163 num.push(num1 / num2);
164 break;
165 }
166 op.pop();
167 }
168 if (!ok) continue;
169 if (num.top() == ret) {
170 flag = 1;
171 puts("yes");
172 break;
173 }
174 }
175 if (!flag) puts("no");
176 }
177 return 0;
178 }
179