POJ-3295 解题报告

题意简述

输入长度≤100的由K,A,N,C,E,p,q,r,s,t组成的逻辑表达式，其中K,A,N,C,E分别代表与，或，非，条件，等价，小写字母为命题变量。

若该式为永真式，则输出tautology，否则输出not

输入数据有多组，遇0停止输入。

算法分析

考虑表达式最多只有5个变量，真值表最多只有2^5=32种排列，所以选择枚举所有排列判断表达式是否恒真。

使用一个int型变量，从0枚举至31，则其二进制拆分成位后刚好匹配了32种01全排列。在使用时，假设想取出第4位，只需将它&(1000)2，不等0则为1，否则为0。其余位置可类推。

判断一个确定赋值的表达式是否为真，可以参照栈的多项式处理应用。由于不牵扯括号运算所以较为简单。从右向左扫描表达式，遇变量则将其赋值压入栈中。遇单目运算符（not）则对栈顶元素进行操作。遇双目运算符则弹出栈顶两个元素，运算后将结果压回栈中。

最后判断栈顶剩余元素（其实栈中只剩下一个元素）是否为1即可。

Problem Status: AC。时间0ms，内存360k

程序样例

#include<stdio.h>
#include<string.h>

int judge(char c[], int f1, int l) {
  int s[100] = {0}, h, p, f[5] = {1}, i;
  for (i = 1; i < 5; i++)
    f[i] = f[i - 1] * 2;
  for (i = 0; i < 5; i++) {
    f[i] = f[i] & f1;
    if (f[i] > 0) f[i] = 1;
  }
  p = l - 1;
  h = 0;
  while (p >= 0) {
    switch (c[p]) {
    case 'p':
      s[h] = f[0];
      h++;
      break;
    case 'q':
      s[h] = f[1];
      h++;
      break;
    case 'r':
      s[h] = f[2];
      h++;
      break;
    case 's':
      s[h] = f[3];
      h++;
      break;
    case 't':
      s[h] = f[4];
      h++;
      break;
    case 'K':
      h = h - 2;
      if (s[h] == 1 && s[h + 1] == 1) h++;
      else {
        s[h] = 0;
        h++;
      }
      break;
    case 'A':
      h = h - 2;
      if (s[h] == 0 && s[h + 1] == 0) h++;
      else {
        s[h] = 1;
        h++;
      }
      break;
    case 'N':
      h = h - 1;
      if (s[h] == 0) s[h] = 1;
      else s[h] = 0;
      h++;
      break;
    case 'C':
      h = h - 2;
      if (s[h] == 0 && s[h + 1] == 1) h++;
      else {
        s[h] = 1;
        h++;
      }
      break;
    case 'E':
      h = h - 2;
      if (s[h] == s[h + 1]) s[h] = 1;
      else s[h] = 0;
      h++;
      break;
    }
    p--;
  }
  return s[0];
}

int main() {
  char c[100];
  int i, l;
  scanf("%s", c);
  while (strcmp(c, "0") != 0) {
    l = strlen(c);
    for (i = 0; i < 32; i++)
      if (!judge(c, i, l)) {
        printf("not\n");
        break;
      }
    if (i == 32) printf("tautology\n");
    scanf("%s", c);
  }
  return 0;
}