《Cracking the Coding Interview》——第9章：递归和动态规划——题目11

 1 // 9.11 For a boolean expression and a target value, calculate how many ways to use parentheses on the expression to achieve that value.
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 
 7 void booleanExpressionParentheses(string exp, int target, int &result, vector<string> &one_path, vector<vector<string> > &path)
 8 {
 9     if ((int)exp.length() == 1) {
10         if (exp[0] - ‘0‘ == target) {
11             path.push_back(one_path);
12             ++result;
13         }
14         return;
15     }
16     
17     string new_exp;
18     int i, j;
19     for (i = 1; i < (int)exp.length(); i += 2) {
20         new_exp = "";
21         
22         for (j = 0; j < i - 1; ++j) {
23             new_exp.push_back(exp[j]);
24         }
25         
26         if (exp[i] == ‘&‘) {
27             new_exp.push_back(((exp[i - 1] - ‘0‘) & (exp[i + 1] - ‘0‘)) + ‘0‘);
28         } else if (exp[i] == ‘|‘) {
29             new_exp.push_back(((exp[i - 1] - ‘0‘) | (exp[i + 1] - ‘0‘)) + ‘0‘);
30         } else if (exp[i] == ‘^‘) {
31             new_exp.push_back(((exp[i - 1] - ‘0‘) ^ (exp[i + 1] - ‘0‘)) + ‘0‘);
32         }
33         
34         for (j = i + 2; j < (int)exp.length(); ++j) {
35             new_exp.push_back(exp[j]);
36         }
37         one_path.push_back(new_exp);
38         booleanExpressionParentheses(new_exp, target, result, one_path, path);
39         one_path.pop_back();
40     }
41 }
42 
43 int main()
44 {
45     int result;
46     int target;
47     int i, j;
48     string exp;
49     vector<vector<string> > path;
50     vector<string> one_path;
51     
52     while (cin >> exp >> target) {
53         result = 0;
54         one_path.push_back(exp);
55         booleanExpressionParentheses(exp, target, result, one_path, path);
56         one_path.pop_back();
57         for (i = 0; i < (int)path.size(); ++i) {
58             cout << "Path " << i + 1 << endl;
59             for (j = 0; j < (int)path[i].size(); ++j) {
60                 cout << path[i][j] << endl;
61             }
62             cout << endl;
63         }
64 
65         for (i = 0; i < (int)path.size(); ++i) {
66             path[i].clear();
67         }
68         path.clear();
69         one_path.clear();
70 
71         cout << "Total number of ways to achieve the target value is " << result << "." << endl;
72     }
73     
74     return 0;
75 }