基于python实现通过真值表判断一个逻辑表达式

完整代码：https://download.csdn.net/download/weixin_55771290/87428985

设计要求

1．问题描述

一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一程序，通过真值表判断一个逻辑表达式属于哪一类。

2．需求分析

1. 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”，“&”和“~”,分别表示或、与和非，运算优先程度递增，但可以由括号改变，即括号内的运算优先。逻辑变元为大写字母，表达式中任何地方都可以含有多个空格符。
2. 若是重言式或矛盾式，显示“True forever”或“False forever”，否则显示“Satisfactible”。若用户对表达式中变元取一组值，程序就求出并显示逻辑表达式的值。在判断的结果下方同时列出真值表。
3. 对于一个简单的表达式求值运算规则如下：
4. 
   

a) 从左至右依次计算。

b) 先取反， 然后相与，后相或。

c) 先括号内，后括号外。

二、准备知识

我们可以将逻辑表达式的计算类比算术表达式的计算，通常借助堆栈来实现按运算符的优先级完成表达式的求值计算：一个是存放运算符的栈，另一个是存放变量或中间结果的栈。回顾一下中缀表达式转后缀表达式并计算的计算过程：

1、任何中缀表达式都由运算数，运算符，括号这三部分组成，其中括号的优先级最高，其次是乘除，最后是加减。

2、从左到右遍历中缀表达式，若遇到运算数时，则直接将压入数据栈。

3、若为运算符，以下几种情况直接将符号入栈：

栈为空；栈顶为左括号；该符号优先级比栈顶符号的优先级高。

4、若遇到右括号，表达括号内的中缀表达式已经扫描完毕，则执行计算步骤：从运算符栈弹出一个运算符号，从数据栈弹出两个数字进行一次运算并将结果入栈。重复此步骤直至遇到左括号，将左括号出栈。

5、如果该运算符的优先级小于或等于栈顶运算符的优先级时，重复4中的计算步骤，直到运算符栈空或栈顶为左括号。

6、最后扫描到中缀表达式的末尾，继续执行之前的计算步骤直到运算符栈空。

三、概要设计

算法整体流程

如图figure1所示，我们算法的整体思路非常清晰；对于给定的逻辑表达式，我们先解析得到所有的变元，然后我们依次给变元赋值0和1；对于由n个变元组成的逻辑表达式，那么最终将得到2^n个不含任何变元的逻辑表达式；最后我们通过将这2^n个表达式一一计算得到真值表；通过真值表判定该逻辑表达式是否是重言式或者矛盾式；对于有追加的赋值，一种方法是直接查刚才计算得出的真值表，另一种途径是提前将追加的变元赋值，然后再解析、算真值表；为了代码的复用，我们使用了第二种方法。

四、详细设计

代码的整体结构如下所示，我们采用了面向对象的编程思想；定义LogicExpression类完成所有功能; 定义字典代表所有字符符号的优先级；定义__init__方法完成对象的初始化；定义parse方法完成变元的解析；定义generate方法完成真值表（变元部分）的生成；operate方法、process方法、solve方法均为具体计算表达式的方法；定义main方法整合所有计算过程；定义conclusion方法完成最后表达式的判定；

classLogicExpression:priority={'(':4,'~':3,'&':2,'|':1}#定义符号的优先级def__init__(self,expression)defparse(self):defgenerate(self):defoperate(self,symbol,arg):#不定长参数defprocess(self,data,opt):defsolve(self,exp):defmain(self):@propertydefconclusion(self):

1.输入表达式

初始化部分非常简单,只是获取用户输入的表达式并删去多余的空格

def__init__(self,expression):self.expression=expression.replace(' ','')#初始表达式、并删掉多余空格

2.解析变量

而解析表达式，获得变元这部分我们使用了python的正则表达式模块，我们规定变元的命名标准同代码中变元的命名标准相同；此外用set去除出现过不止一次的变元；最后按照变元的原始顺序排序。

defparse(self):pattern=re.compile(r'[a-zA-Z_]w')# 变量规则与代码中变量定义规则相同 字母、 数字、 下划线组合,数字不能开头vars1=pattern.findall(self.expression)# 解析成变量列表(待去重)vars2=list(set(vars1))# 去重vars2.sort(key=vars1.index)# 保持原来顺序不变returnvars2

3.遍历赋值

在编历赋值这块，我们使用了python的自建模块itertools.product函数快速生成组合元祖；然后直接将变元用0和1替换；在返回时，使用yield函数依次返回一种组合，减少内存开销；

defgenerate(self):l=[0,1]forcaseinproduct([l]len(self.vars)):#case为生成的组合元祖： 两个变量的情况下为(0, 0)(0, 1)(1, 0)(1, 1)exp=self.expressionforiinrange(len(self.vars)):exp=exp.replace(self.vars[i],str(case[i]))yieldexp# 使用python的迭代器依次返回代入值后的表达式

4.计算表达式的值

计算表达式的值(不带变元)是整个代码的核心；我们的思想是维护两个栈分别存放逻辑符号和逻辑值。遍历表达式中的所有字符，按照优先级规则和栈内情况具体决定压栈和出栈，具体标准请参照下图：

1. 对于逻辑值直接进逻辑栈；
2. 遇到 ) 则进行出栈计算直到逻辑符号栈顶为 ( ,并将 ( 出栈
3. 逻辑符号直接进栈的三种情况：符号栈为空、符号栈顶为（、符号栈顶符号的优先级小于该符号，在这三种情况下直接进栈
4. 其余情况下，根据栈顶符号类型，取出相应数量的逻辑值进行运算，然后压入逻辑值栈；如此往复，直至当前符号满足进栈规则3
5. 最后如果符号栈尚有元素，则继续运算
6. 逻辑值栈最后存在的值即为表达式的解

Figure2 出入栈标准

对应代码如下：

defsolve(self,exp):data=[]# 逻辑栈opt=[]# 操作符号栈foriinexp:ifi.isdigit():#如果是数字则直接进逻辑

其中还定义了两个子函数process和operate; processs 函数的作用是模拟取出符号栈和逻辑值栈元素运算的过程；operate函数作用是具体计算一个！&和|的运算，代码示例如下：

defoperate(self,symbol,arg):#不定长参数'''symbol:逻辑符号~&|arg:逻辑值(不定长)'''ifsymbol=='~'andlen(arg)==1:#~的情况returnnotarg[0]elifsymbol=='&'andlen(arg)==2:# & 的情况returnarg[0]andarg[1]elifsymbol=='|'andlen(arg)==2:# | 的情况returnarg[0]orarg[1]else:raise"operate error"defprocess(self,data,opt):'''data:逻辑值栈存放true和falseopt:符号栈存放~&|'''symbol=opt.pop()ifsymbol=='~':logic1=data.pop()data.append(self.operate(symbol,logic1))returnelifsymbolin('&','|'):logic1=data.pop()logic2=data.pop()data.append(self.operate(symbol,logic1,logic2))return

5.判断永真或者永假

最后判断是否永真或者永假，非常简单只要判断结果列表里面是否存在true（false）的情况

@propertydefconclusion(self):ifFalsenotinself.results:return'True forever'elifTruenotinself.results:return'False forever'else:return'Satisfactible'

6.网页部分

我们还设计了一个小网页用作交互，如下图所示：

网页部分使用python的flask引擎搭建；后端也很简单；分别对url的get请求和post请求做响应；post请求中调用实现好的LogicExpression类运算,而get请求则直接返回原始网页。

@app.route("/",methods=["GET","POST"])defmain():ifrequest.method=='POST':expression=request.form.get('expression')addition=request.form.get('addition')ifaddition:expression=withAddition(expression,addition)le=LogicExpression(expression)varss,results,conclusion=le.vars,le.results,le.conclusionlogic_table=tuple(product([[0,1]]len(varss)))returnrender_template("index.html",form=request.form,logic_table=logic_table,varss=varss,results=results,conclusion=conclusion)else:returnrender_template("index.html",form={})

Figure3 网页外观

Figure4 判断结果

五、程序测试

1. 第一次进行测试时，发现输入逻辑表达式 P | P & Q 穷举出来的结果有三个False，一个True，与实际不符（正确结果应为两个False，两个True），检查发现程序没有考虑到运算符 & 和 | 之间的优先级不同，所以先算了表达式前半部分，相当于是计算了（P | P）& Q 的结果。更正后自定义了各个符号对应的优先级，在符号出入栈时增加了比较优先级的步骤，再次进行测试。
2. 为了避免人工构造逻辑表达式产生的局限性，我们编写了一段程序，随机生成了5000条表达式，保证了测试的覆盖完整性，提高了测试效率。生成的部分测试用例如图所示：
3. 
   

Figure5 测试用例

3. 人工验证结果难免疏漏，且想要人工验证5000条结果必定耗时巨大。为了更好的验证结果的正确性，我们选用了事先写好的两段不同的程序运行上述的5000条测试用例，再将两者的结果进行比对，结果完全一致。以下是其中一个程序的部分运行结果，及两边结果的比对：
   

Figure6 程序运行结果

Figure7 结果比对

六、总结

该程序运用了 python语言对数据的存储结构和算法进行描述，实现了命题逻辑公式的类型判断。设输入的逻辑表达式的长度为m，其中有n个变元，则算法时间复杂度为T(n)=O(2^n)，两个堆栈的长度不超过m，空间复杂度为O(m)。该程序的优势在于代码简洁清晰，空间复杂度低，缺点在于算法时间复杂度没有得到很好的改善，仍有待优化。这次的实践要求我们结合所学，根据实际问题合理地选择相应的存储结构，并设计出有效算法，较之前的理论课来说更具有挑战性。从选题到查找资料、确定思路，从源代码的完成、调试、修改、完善到撰写报告，我们加深了对算法与数据结构概念的理解，强化了面向对象的程序设计理念，培养了综合运用所学知识处理实际问题的能力。 实践过程中，我们经过查找参考资料、技术手册和撰写文档，进一步培养了软件工程师的综合素质；而通过验证自己设计的算法的正确性，我们学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。这次实践还让我们复习到了离散数学的相关知识，通过不断探寻改进更优解、写出简洁优美的算法，我们更为直观的体会到了算法之美。