- 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.
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.]
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.
For each line read in, echo it back, followed by its correctness as a WFF, followed (if a WFF) with its category (tautology, contradiction, or contingent). In processing an input line, immediately terminate and report the line as not a WFF if you encounter an unrecognized operator (even though it may fail to be well-formed in another way as well). If it has extraneous text following the WFF, report it as incorrect. If it has insufficient operands, report that. Use exactly the format shown in the Sample Output below.
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
- 博客 大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 技术大佬：我去，你写的 switch 语句也太老土了吧
- 博客 上班一个月，后悔当初着急入职的选择了
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 程序员写出这样的代码，能不挨骂吗？
- 博客 我说我不会算法，阿里把我挂了。
- 博客 带了6个月的徒弟当了面试官，而身为高级工程师的我天天修Bug......
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 C语言的灵魂之指针
- 博客 为什么程序员做外包会被瞧不起？
- 博客 10个提升效率的编程好习惯
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发
- 博客 《Java经典编程365例》000：学妹的优秀成绩单
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 Python爬虫，高清美图我全都要（彼岸桌面壁纸）
- 博客 无代码时代来临，程序员如何保住饭碗？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 6年开发经验女程序员，面试京东Java岗要求薪资28K
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 Java岗开发3年，公司临时抽查算法，离职后这几题我记一辈子
- 博客 都前后端分离了，咱就别做页面跳转了！统统 JSON 交互
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 程序员是做全栈工程师好？还是专注一个领域好？