?

本題中最多5個(gè)命題變項(xiàng)：p,q,r,s,t

每個(gè)有0,1兩種取值，所以總共32種情況，分別枚舉即可。

對(duì)于每種情況，計(jì)算表達(dá)式的值，如果有結(jié)果為0的則輸出not

難點(diǎn)在于如何計(jì)算表達(dá)式的值，我們采用遞歸的方法，把表達(dá)式分為一或兩個(gè)子表達(dá)式，并把參數(shù)end（本表達(dá)式的結(jié)束位置）傳給上一層，一遍上一層獲取第二個(gè)子表達(dá)式的起始位置。最后通過(guò)兩個(gè)子表達(dá)式的結(jié)束位置，得到整個(gè)表達(dá)式的結(jié)束位置。

end是本表達(dá)式的最后一位的下標(biāo)，即本表達(dá)式的長(zhǎng)度減一。

所以 end = 2 + end1 + end2;

1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <cstdlib> 5 using namespace std; 6 7 string p; 8 bool v[5]; 9 10 bool getValue(string p, int &end) 11 { 12 bool a, b; 13 int end1, end2; 14 15 if (p[0] >= 'p') 16 { 17 end = 0; 18 return v[p[0] - 'p']; 19 } 20 if (p[0] == 'N') 21 { 22 a = getValue(p.substr(1, p.length() - 1), end1); 23 end = end1 + 1; 24 return !a; 25 } 26 a = getValue(p.substr(1, p.length() - 1), end1); 27 b = getValue(p.substr(end1 + 2, p.length() - 1), end2); 28 end = 2 + end1 + end2; 29 switch (p[0]) 30 { 31 case 'K': 32 return a && b; 33 case 'A': 34 return a || b; 35 case 'C': 36 return !a || b; 37 case 'E': 38 return !(a ^ b); 39 } 40 return 0; 41 } 42 43 int main() 44 { 45 bool ok; 46 47 while (getline(cin, p) && p[0] != '0') 48 { 49 ok = true; 50 for (int i = 0; i < 32; i++) 51 { 52 for (int j = 0; j < 5; j++) 53 v[j] = (i >> j) % 2; 54 int x; 55 if (!getValue(p, x)) 56 { 57 ok = false; 58 break; 59 } 60 } 61 if (ok) 62 cout << "tautology" << endl; 63 else 64 cout << "not" << endl; 65 } 66 return 0; 67 }

?轉(zhuǎn)自http://www.cnblogs.com/rainydays/archive/2011/02/01/1948678.html

轉(zhuǎn)載于:https://www.cnblogs.com/gj-Acit/archive/2013/01/30/2883618.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Tautology（poj3295）（DFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。