Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem D: Tautology

WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:

• p, q, r, s, and t are WFFs
• if w is a WFF, Nw is a WFF
• if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

The meaning of a WFF is defined as follows:

• p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
• K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.

Definitions of K, A, N, C, and E

w  x	Kwx	Awx	Nw	Cwx	Ewx
1  1	1	1	0	1	1
1  0	0	1	0	0	0
0  1	0	1	1	1	0
0  0	0	0	1	1	1

A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.

You must determine whether or not a WFF is a tautology.

Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case. For each test case, output a line containing tautology or not as appropriate.

Sample Input

ApNp
ApNq
0

Possible Output for Sample Input

tautology
not

---

Gordon V. Cormack

題目給定一個前序式，小寫表示運算元(0/1)，大寫表示運算子。
tautology 的定義是，不管變數值為何，運算出來的值恆為真(true 1)。
窮舉所有變數的分配方式 2^5 = 32 種，進行前序運算。

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int main() {
    char s[1005];
    int i, j;
    while(scanf("%s", s) && s[0] != '0') {
        int ret = 1, len = strlen(s);
        int a, b;
        for(i = 0; i < 32; i++) {
            stack<int> stk;
            for(j = len-1; j >= 0; j--) {
                if(s[j] >= 'p') {
                    int val = (i>>(s[j]-'p'))&1;
                    stk.push(val);
                } else {
                    a = stk.top(), stk.pop();
                    if(s[j] != 'N') {
                        b = stk.top(), stk.pop();
                    }
                    if(s[j] == 'K')
                        stk.push(a&b);
                    if(s[j] == 'A')
                        stk.push(a|b);
                    if(s[j] == 'N')
                        stk.push(!a);
                    if(s[j] == 'C')
                        stk.push(!(a&(!b)));
                    if(s[j] == 'E')
                        stk.push(a == b);
                }
            }
            ret &= stk.top();
        }
        puts(ret ? "tautology" : "not");
    }
    return 0;
}