首页 > ACM题库 > HDU-杭电 > HDU 3155-Symbolic Logic Mechanization[解题报告]HOJ
2014
03-06

HDU 3155-Symbolic Logic Mechanization[解题报告]HOJ

Symbolic Logic Mechanization

问题描述 :

Marvin, the robot with a brain the size of a planet, followed some . . . markedly less successful robots as the product line developed. One such was Monroe, the robot ― except, to help him recognize his name, he was referred to as Moe. He is sufficiently mentally challenged that he needs external assistance to handle symbolic logic.

Optimal Strategy for the ICPC

Polish notation is the prefix symbolic logic notation developed by Jan Lukasiewicz (1929). [Hence postfix expressions are referred to as being in Reverse Polish Notation ― RPN.] The notation developed by Lukasiewicz (referred to as PN below) uses upper-case letters for the logic operators and lower-case letters for logic variables (which can only be true or false). Since prefix notation is self-grouping, there is no need for precedence, associativity, or parentheses, unlike infix notation. In the following table the PN operator is shown, followed by its operation. Operators not having exactly equivalent C/C++/Java operators are shown in the truth table (using 1 for true and 0 for false). [The operator J is not found in Lukasiewicz’ original work but is included from A.N.Prior’s treatment.]

Optimal Strategy for the ICPC    Optimal Strategy for the ICPC

For every combination of PN operators and variables, an expression is a "well-formed formula" (WFF) if and only if it is a variable or it is a PN operator followed by the requisite number of operands (WFF instances). A combination of symbols will fail to be a "well-formed formula" if it is composed of a WFF followed by extraneous text, it uses an unrecognized character [uppercase character not in the above table or a non-alphabetic character], or it has insufficient operands for its operators. For invalid expressions, report the first error discovered in a left-toright scan of the expression. For instance, immediately report an error on an invalid character. If a valid WFF is followed by extraneous text, report that as the error, even if the extraneous text has an invalid character.

In addition, every WFF can be categorized as a tautology (true for all possible variable values), a contradiction (false for all possible variable values), or a contingent expression (true for some variable values, false for other variable values).

The simplest contingent expression is simply ‘p‘, true when p is true, false when p is false. One very simple contradiction is "KpNp", both p and not-p are true. Similarly, one very simple tautology is "ApNp", either p is true or not-p is true. For a more complex tautology, one expression of De Morgan’s Law is "EDpqANpNq".

输入:

Your program is to accept lines until it receives an empty character string. Each line will contain only alphanumeric characters (no spaces or punctuation) that are to be parsed as potential "WFFs". Each line will contain fewer than 256 characters and will use at most 10 variables. There will be at most 32 non-blank lines before the terminating blank line.

输出:

Your program is to accept lines until it receives an empty character string. Each line will contain only alphanumeric characters (no spaces or punctuation) that are to be parsed as potential "WFFs". Each line will contain fewer than 256 characters and will use at most 10 variables. There will be at most 32 non-blank lines before the terminating blank line.

样例输入:

q
Cp
Cpq
A01
Cpqr
ANpp
KNpp
Qad
CKNppq
JDpqANpNq
CDpwANpNq
EDpqANpNq
KCDpqANpNqCANpNqDpq

样例输出:

q is valid: contingent
Cp is invalid: insufficient operands
Cpq is valid: contingent
A01 is invalid: invalid character
Cpqr is invalid: extraneous text
ANpp is valid: tautology
KNpp is valid: contradiction
Qad is invalid: invalid character
CKNppq is valid: tautology
JDpqANpNq is valid: contradiction
CDpwANpNq is valid: contingent
EDpqANpNq is valid: tautology
KCDpqANpNqCANpNqDpq is valid: tautology

/**
 * ID: ping128
 * LANG: C++
 */

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <math.h>
#include <algorithm>
#include <map>
#include <string.h>

using namespace std;

typedef long long LL;
typedef pair<int, int>PII;
typedef pair<PII, int>PII2;

string s;
int n;
int len;
map<char, int>val;
int value[20];
int at;

int good;

// 1 good
// -1 invalid character
// -2 insufficient operands
// -3 extraneous text

int eva()
{
 // cout << at << " " << s[at] << endl;
 if(good != 1) return 0;
 if(at >= len) 
 {
 good = -2;
 }
 else if(s[at] >= 'a' && s[at] <= 'z')
 {
 return value[val[s[at++]]];
 } 
 else if(s[at] >= 'A' && s[at] <= 'Z')
 {
 at++;
 int x, y;
 switch(s[at - 1])
 {
 case 'C': x = eva(); y = eva(); if(x && !y) return 0; else return 1;
 case 'N': x = eva(); return x ^ 1;
 case 'K': x = eva(); y = eva(); return x & y;
 case 'A': x = eva(); y = eva(); return x | y;
 case 'D': x = eva(); y = eva(); return !(x & y);
 case 'E': x = eva(); y = eva(); return (x == y);
 case 'J': x = eva(); y = eva(); return x ^ y;
 default: good = -1; break;
 }
 }
 else
 {
 good = -1;
 } 
}

int main()
{
 // freopen("g.in", "r", stdin);
 while(cin >> s)
 {
 good = 1;
 len = s.length();
 n = 0;
 val.clear();
 for(int i = 0; i < len; i++ )
 {
 if(s[i] >= 'a' && s[i] <= 'z' && val.find(s[i]) == val.end())
 {
 val[s[i]] = n++;
 }
 }
 
 int ct = 0, cn = 0;
 for(int i = 0; i < 1<<n && good == 1; i++ )
 {
 for(int j = 0; j < n; j++ )
 {
 if(i & (1<<j))
 value[j] = 1;
 else
 value[j] = 0;
 }
 at = 0;
 int res = eva();
 if(good == 1 && at < len) good = -3;
 if(res) ct++;
 else cn++;
 }
 
 cout << s << " is ";
 if(good == 1)
 {
 cout << "valid: ";
 if(ct && cn) cout << "contingent" << endl;
 else if(ct) cout << "tautology" << endl;
 else cout << "contradiction" << endl;
 }
 else if(good == -1)
 {
 cout << "invalid: invalid character" << endl;
 }
 else if(good == -2)
 {
 cout << "invalid: insufficient operands" << endl;
 }
 else
 {
 cout << "invalid: extraneous text" << endl;
 }
 }
 
//while(1);

return 0;
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience