POJ 1779 - Boolean Logic

http://poj.org/problem?id=1779

概要

論理式が与えられるので，それの真理値表を答える．

も論理式

制約

特になし． 変数が小文字のアルファベットなので，最大でも26種類であることはわかる．

解法

真理値表を出力するときに，空白を保存しつつシンボルや演算子の位置に出力しなければならないのがめんどくさい．

論理式をパースするときに，そのシンボルや演算子があったインデックスを覚えておくようにした．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 struct expr
  7 {
  8   int loc;
  9   char v;
 10   expr *lhs, *rhs;
 11   expr(int l, char c) : loc(l), v(c), lhs(0), rhs(0) {}
 12   expr(int l, expr *e) : loc(l), v(0), lhs(e), rhs(0) {}
 13   expr(int l, char o, expr *x, expr *y) : loc(l), v(o), lhs(x), rhs(y) {}
 14   ~expr() { delete lhs; delete rhs; }
 15 
 16   bool eval(const bool *b, string& buf) const
 17   {
 18     bool x;
 19     if (!lhs) {
 20       // symbol
 21       x = b[v-'a'];
 22     } else if (!rhs) {
 23       // neg
 24       x = !lhs->eval(b, buf);
 25     } else {
 26       // binop
 27       bool l = lhs->eval(b, buf);
 28       bool r = rhs->eval(b, buf);
 29       switch (v) {
 30         case '&':
 31           x = l && r;
 32           break;
 33         case '|':
 34           x = l || r;
 35           break;
 36         case '-':
 37           x = !l || r;
 38           break;
 39         case '<':
 40           x = l == r;
 41           break;
 42         default:
 43           cerr << "V = " << v << ", loc = " << loc << endl;
 44           throw "unknown operator";
 45       }
 46     }
 47     buf[loc] = '0' + x;
 48     return x;
 49   }
 50 };
 51 
 52 int skip_white(int i, const string& s)
 53 {
 54   while (i < s.size() && s[i] == ' ') {
 55     ++i;
 56   }
 57   return i;
 58 }
 59 
 60 pair<int,expr*> parse_expr(int i, const string& s);
 61 
 62 pair<int,expr*> parse_factor(int i, const string& s)
 63 {
 64   i = skip_white(i, s);
 65   if (s[i] == '(') {
 66     pair<int,expr*> e = parse_expr(i+1, s);
 67     i = skip_white(e.first, s);
 68     if (s[i] != ')') {
 69       throw "unmatched paren";
 70     }
 71     return make_pair(i+1, e.second);
 72   } else {
 73     return make_pair(i+1, new expr(i, s[i]));
 74   }
 75 }
 76 
 77 pair<int,expr*> parse_term(int i, const string& s)
 78 {
 79   i = skip_white(i, s);
 80   if (s[i] == '!') {
 81     int loc = i;
 82     pair<int,expr*> e = parse_factor(i+1, s);
 83     return make_pair(e.first, new expr(loc, e.second));
 84   } else {
 85     return parse_factor(i, s);
 86   }
 87 }
 88 
 89 inline bool isop(char c) { return c == '&' || c == '|' || c == '-' || c == '<'; }
 90 
 91 pair<int,expr*> parse_expr(int i, const string& s)
 92 {
 93   i = skip_white(i, s);
 94   pair<int,expr*> l = parse_term(i, s);
 95   i = skip_white(l.first, s);
 96   expr *lhs = l.second;
 97   while (i < s.size() && isop(s[i])) {
 98     char op = s[i];
 99     int loc = i;
100     i = skip_white(i+1, s);
101     if (op == '-' || op == '<') {
102       if (s[i] != '-') {
103         throw "unk1";
104       }
105       loc = i;
106       i = skip_white(i+1, s);
107       if (s[i] != '>') {
108         throw "unk2";
109       }
110       i = skip_white(i+1, s);
111     }
112     pair<int,expr*> r = parse_term(i, s);
113     i = skip_white(r.first, s);
114     lhs = new expr(loc, op, lhs, r.second);
115   }
116   return make_pair(i, lhs);
117 }
118 
119 int main()
120 {
121   string line;
122   while (getline(cin, line)) {
123     vector<char> vars;
124     for (string::const_iterator it = line.begin(); it != line.end(); ++it) {
125       if ('a' <= *it && *it <= 'z') {
126         vars.push_back(*it);
127       }
128     }
129     sort(vars.rbegin(), vars.rend());
130     vars.erase(unique(vars.begin(), vars.end()), vars.end());
131     const int N = vars.size();
132 
133     expr *e = parse_expr(skip_white(0, line), line).second;
134     bool b[30];
135     string buf(line.size(), ' ');
136     cout << line << endl;
137     for (unsigned s = 0; s < (1<<N); s++) {
138       for (int i = 0; i < N; i++) {
139         b[vars[i]-'a'] = (s & (1<<i)) != 0;
140       }
141       e->eval(b, buf);
142       cout << buf << endl;
143     }
144     cout << endl;
145     delete e;
146   }
147   return 0;
148 }
poj/1779.cc