簡(jiǎn)介這份資源是面向計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生的數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告主題為重言式判別適合正在完成課程設(shè)計(jì)或需要理解邏輯表達(dá)式求值的中級(jí)學(xué)習(xí)者參考。文檔圍繞真值表判別邏輯表達(dá)式類型展開(kāi)涵蓋輸入處理、運(yùn)算符優(yōu)先級(jí)、堆棧求值及二叉樹(shù)構(gòu)造等核心內(nèi)容并給出完整的問(wèn)題分析、數(shù)據(jù)結(jié)構(gòu)選擇與概要設(shè)計(jì)。壓縮包內(nèi)僅含1個(gè)doc文件約293KB為合肥學(xué)院20162017學(xué)年第一學(xué)期的課程設(shè)計(jì)報(bào)告包含題目描述、基本要求、測(cè)試數(shù)據(jù)及詳細(xì)算法推導(dǎo)。讀者可從中獲取完整的課程設(shè)計(jì)框架、算符優(yōu)先關(guān)系表、中序遍歷二叉樹(shù)求值思路以及將邏輯表達(dá)式構(gòu)造成二叉樹(shù)的實(shí)現(xiàn)步驟對(duì)掌握棧與二叉樹(shù)在表達(dá)式求值中的應(yīng)用有直接幫助。目前已有147人學(xué)習(xí)適合作為課程設(shè)計(jì)參考或算法練習(xí)素材。1. 重言式判別到底在判什么從真值表到可復(fù)現(xiàn)的課程設(shè)計(jì)很多同學(xué)第一次看到“重言式判別”這個(gè)題目第一反應(yīng)是“不就是列真值表嗎”然后打開(kāi)編輯器準(zhǔn)備寫一個(gè)二重循環(huán)。真到動(dòng)手才發(fā)現(xiàn)命題變?cè)欢嗾嬷当硇袛?shù)按 2 的 n 次方膨脹n10 就是 1024 行n20 直接上百萬(wàn)行內(nèi)存和遞歸棧雙雙告急。這個(gè)課程設(shè)計(jì)真正要解決的問(wèn)題不是“會(huì)不會(huì)列真值表”而是“怎么把任意一個(gè)命題公式在有限步驟內(nèi)判定它是不是重言式并且給出可解釋的中間結(jié)果”。它適合兩類人一類是正在做數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)、需要一份能跑通、能答辯、能寫進(jìn)報(bào)告的完整方案的同學(xué)另一類是想借這個(gè)題目把棧、樹(shù)、遞歸下降、表達(dá)式求值這幾塊知識(shí)串起來(lái)練一遍的開(kāi)發(fā)者。核心鏈路其實(shí)就四步讀入公式字符串、解析成表達(dá)式樹(shù)、按變?cè)≈登笾?、枚舉所有賦值判斷是否恒真。聽(tīng)起來(lái)簡(jiǎn)單但每一步都有坑尤其是解析和剪枝直接決定你的程序是“能跑樣例”還是“能過(guò)全部測(cè)試”。2. 從公式字符串到表達(dá)式樹(shù)解析器怎么搭才不翻車2.1 為什么不能直接對(duì)字符串做替換求值最常見(jiàn)的偷懶做法是把變?cè)?0/1 替換然后用某種方式算結(jié)果。問(wèn)題在于運(yùn)算符優(yōu)先級(jí)和括號(hào)嵌套。比如p∨q∧?r如果你從左到右替換再算∧和∨的優(yōu)先級(jí)就亂了。更麻煩的是?是一元運(yùn)算符??p和?(p∧q)的處理方式完全不同。字符串替換法在簡(jiǎn)單樣例上能過(guò)一旦遇到嵌套括號(hào)和混合運(yùn)算符就翻車這是血淚經(jīng)驗(yàn)。正確做法是先做詞法分析把字符串切成 token 序列再用遞歸下降或調(diào)度場(chǎng)算法轉(zhuǎn)成表達(dá)式樹(shù)。表達(dá)式樹(shù)的好處是求值時(shí)只需要后序遍歷邏輯清晰剪枝時(shí)可以在樹(shù)上做標(biāo)記輸出中間結(jié)果時(shí)也能按樹(shù)形結(jié)構(gòu)展示答辯時(shí)很加分。2.2 詞法分析與 token 定義先定義 token 類型。命題變?cè)脝蝹€(gè)小寫字母表示運(yùn)算符包括?非、∧與、∨或、→蘊(yùn)含、?等價(jià)括號(hào)用(和)。為了兼容鍵盤輸入通常還要支持!、、|、-、-這些替代寫法。# 詞法分析把公式字符串切成 token 列表 # 支持符號(hào)變?cè)?a-z運(yùn)算符 ! | - - ( ) def tokenize(formula): tokens [] i 0 while i len(formula): ch formula[i] if ch.isspace(): i 1 continue if ch.isalpha() and ch.islower(): tokens.append((VAR, ch)) i 1 elif ch !: tokens.append((NOT, !)) i 1 elif ch : tokens.append((AND, )) i 1 elif ch |: tokens.append((OR, |)) i 1 elif formula[i:i3] -: tokens.append((IFF, -)) i 3 elif formula[i:i2] -: tokens.append((IMP, -)) i 2 elif ch (: tokens.append((LPAREN, ()) i 1 elif ch ): tokens.append((RPAREN, ))) i 1 else: raise ValueError(f非法字符: {ch} 位置 {i}) return tokens這段代碼的關(guān)鍵點(diǎn)先匹配三字符的-再匹配兩字符的-最后匹配單字符。順序反了就會(huì)把-切成和-直接報(bào)錯(cuò)。變?cè)恢С謫蝹€(gè)小寫字母這是課程設(shè)計(jì)的常見(jiàn)約定如果想支持多字符變?cè)枰~外加分隔符或最長(zhǎng)匹配邏輯。2.3 遞歸下降構(gòu)建表達(dá)式樹(shù)有了 token 序列接下來(lái)按優(yōu)先級(jí)遞歸下降。優(yōu)先級(jí)從低到高等價(jià) 蘊(yùn)含 或 與 非。每一層對(duì)應(yīng)一個(gè)解析函數(shù)。# 表達(dá)式樹(shù)節(jié)點(diǎn)op 為運(yùn)算符left/right 為子節(jié)點(diǎn)var 為變?cè)?class Node: def __init__(self, opNone, leftNone, rightNone, varNone): self.op op self.left left self.right right self.var var # 遞歸下降解析器 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (None, None) def consume(self, expected_typeNone): tok self.peek() if expected_type and tok[0] ! expected_type: raise ValueError(f期望 {expected_type}實(shí)際 {tok[0]}) self.pos 1 return tok def parse(self): node self.parse_iff() if self.pos ! len(self.tokens): raise ValueError(解析未完成存在多余 token) return node def parse_iff(self): node self.parse_imp() while self.peek()[0] IFF: self.consume(IFF) right self.parse_imp() node Node(op-, leftnode, rightright) return node def parse_imp(self): node self.parse_or() while self.peek()[0] IMP: self.consume(IMP) right self.parse_or() node Node(op-, leftnode, rightright) return node def parse_or(self): node self.parse_and() while self.peek()[0] OR: self.consume(OR) right self.parse_and() node Node(op|, leftnode, rightright) return node def parse_and(self): node self.parse_not() while self.peek()[0] AND: self.consume(AND) right self.parse_not() node Node(op, leftnode, rightright) return node def parse_not(self): if self.peek()[0] NOT: self.consume(NOT) child self.parse_not() return Node(op!, leftchild) return self.parse_atom() def parse_atom(self): tok self.peek() if tok[0] VAR: self.consume(VAR) return Node(vartok[1]) elif tok[0] LPAREN: self.consume(LPAREN) node self.parse_iff() self.consume(RPAREN) return node else: raise ValueError(f意外的 token: {tok})這里有幾個(gè)容易寫錯(cuò)的地方。第一parse_iff和parse_imp用 while 循環(huán)處理左結(jié)合但蘊(yùn)含在邏輯上通常是右結(jié)合課程設(shè)計(jì)里如果沒(méi)特別要求按左結(jié)合處理也能過(guò)大部分測(cè)試但答辯時(shí)可能被追問(wèn)。第二parse_not遞歸調(diào)用自己這樣??p會(huì)生成兩層 NOT 節(jié)點(diǎn)求值時(shí)自然正確。第三parse_atom里遇到左括號(hào)后調(diào)用parse_iff保證括號(hào)內(nèi)完整解析。2.4 收集變?cè)c樹(shù)的后序遍歷求值解析完成后遍歷樹(shù)收集所有變?cè)ブ睾笈判虻玫阶冊(cè)斜?。求值時(shí)傳入一個(gè)賦值字典后序遍歷計(jì)算每個(gè)節(jié)點(diǎn)的布爾值。# 收集變?cè)?def collect_vars(node, acc): if node is None: return if node.var: acc.add(node.var) collect_vars(node.left, acc) collect_vars(node.right, acc) # 后序遍歷求值 def evaluate(node, assignment): if node.var: return assignment[node.var] if node.op !: return not evaluate(node.left, assignment) left_val evaluate(node.left, assignment) right_val evaluate(node.right, assignment) if node.op : return left_val and right_val if node.op |: return left_val or right_val if node.op -: return (not left_val) or right_val if node.op -: return left_val right_val raise ValueError(f未知運(yùn)算符: {node.op})蘊(yùn)含p→q等價(jià)于?p∨q等價(jià)p?q就是pq。這兩個(gè)定義必須記牢否則真值表全錯(cuò)。求值函數(shù)用遞歸實(shí)現(xiàn)深度等于樹(shù)高一般公式不會(huì)太深不用擔(dān)心棧溢出。3. 枚舉賦值與剪枝2^n 怎么壓到能跑3.1 樸素枚舉的邊界在哪里收集到 k 個(gè)變?cè)竺杜e 0 到 2^k - 1 的每個(gè)整數(shù)轉(zhuǎn)成二進(jìn)制位作為賦值。k15 時(shí) 32768 次求值秒出k20 時(shí) 1048576 次大概幾秒k25 時(shí) 3355 萬(wàn)次Python 可能要幾分鐘。課程設(shè)計(jì)的測(cè)試用例通常不會(huì)超過(guò) 20 個(gè)變?cè)绻阆胱尦绦蚋€(wěn)剪枝是必須的。3.2 基于短路求值的剪枝表達(dá)式樹(shù)求值時(shí)和|有短路特性False x直接為 FalseTrue | x直接為 True。在枚舉賦值時(shí)如果某棵子樹(shù)已經(jīng)能確定整個(gè)公式的真值就不需要繼續(xù)枚舉剩余變?cè)?。?shí)現(xiàn)方式是在求值函數(shù)里返回一個(gè)特殊標(biāo)記表示“已確定”或“不確定”。更實(shí)用的剪枝是先對(duì)公式做一次部分賦值如果已經(jīng)能判定為假就跳過(guò)該分支下所有完整賦值。這需要把枚舉改成遞歸形式逐層給變?cè)x值每賦一個(gè)就嘗試求值如果確定假就回溯。# 遞歸枚舉 剪枝 def is_tautology(node, variables): n len(variables) assignment {} # 嘗試部分賦值如果已經(jīng)能確定為假直接剪枝 def dfs(idx): if idx n: return evaluate(node, assignment) var variables[idx] for val in (False, True): assignment[var] val # 部分賦值求值如果已經(jīng)確定為假跳過(guò) result try_evaluate(node, assignment) if result is False: continue if not dfs(idx 1): return False return True # 部分賦值求值未賦值的變?cè)祷?None運(yùn)算符按三值邏輯處理 def try_evaluate(node, assign): if node.var: return assign.get(node.var, None) if node.op !: v try_evaluate(node.left, assign) return None if v is None else (not v) l try_evaluate(node.left, assign) r try_evaluate(node.right, assign) if node.op : if l is False or r is False: return False if l is None or r is None: return None return l and r if node.op |: if l is True or r is True: return True if l is None or r is None: return None return l or r if node.op -: if l is False or r is True: return True if l is None or r is None: return None return (not l) or r if node.op -: if l is None or r is None: return None return l r return None return dfs(0)三值邏輯是剪枝的核心None表示不確定False和True表示已確定。只要有一個(gè) False 就是 False|只要有一個(gè) True 就是 True蘊(yùn)含只要前件 False 或后件 True 就是 True。這樣在枚舉早期就能砍掉大量分支。3.3 用真值表驗(yàn)證剪枝正確性剪枝容易寫出 bug必須用樸素枚舉做對(duì)照。對(duì)小規(guī)模變?cè)猭8同時(shí)跑樸素枚舉和剪枝版本比較結(jié)果是否一致。如果一致再逐步增大 k 觀察性能差異。# 對(duì)照測(cè)試 def brute_force_tautology(node, variables): n len(variables) for mask in range(1 n): assignment {} for i, var in enumerate(variables): assignment[var] bool((mask i) 1) if not evaluate(node, assignment): return False return True # 測(cè)試用例 formulas [ p|!p, # 重言式 p!p, # 矛盾式 p-p, # 重言式 p-q, # 非重言式 (p-q)(q-r)-(p-r), # 重言式假言三段論 ] for f in formulas: tokens tokenize(f) tree Parser(tokens).parse() vars_set set() collect_vars(tree, vars_set) variables sorted(vars_set) bf brute_force_tautology(tree, variables) pr is_tautology(tree, variables) print(f{f}: 樸素{bf}, 剪枝{pr}, 一致{bfpr})跑一遍就能發(fā)現(xiàn)剪枝版本在重言式上優(yōu)勢(shì)明顯因?yàn)橐坏┠硞€(gè)分支全為真后續(xù)分支會(huì)被快速跳過(guò)。但在矛盾式上剪枝反而可能因?yàn)轭l繁的三值判斷增加常數(shù)開(kāi)銷所以小規(guī)模時(shí)兩者差距不大。4. 避坑與排查課程設(shè)計(jì)里最容易翻車的五個(gè)點(diǎn)4.1 運(yùn)算符優(yōu)先級(jí)寫反導(dǎo)致結(jié)果全錯(cuò)現(xiàn)象簡(jiǎn)單公式p|qr的結(jié)果和預(yù)期不符真值表里pTrue, qFalse, rFalse時(shí)輸出 False但按優(yōu)先級(jí)應(yīng)該是 True。原因解析時(shí)先處理了|再處理導(dǎo)致被當(dāng)成低優(yōu)先級(jí)。遞歸下降的調(diào)用順序必須從低優(yōu)先級(jí)到高優(yōu)先級(jí)iff → imp → or → and → not → atom。解決檢查每個(gè) parse 函數(shù)調(diào)用的下一級(jí)函數(shù)是否正確。parse_or應(yīng)該調(diào)用parse_and而不是反過(guò)來(lái)。寫完后用p|qr和(p|q)r兩個(gè)公式對(duì)比前者等價(jià)于p|(qr)后者強(qiáng)制括號(hào)結(jié)果不同才算對(duì)。4.2 變?cè)占z漏導(dǎo)致枚舉不全現(xiàn)象公式pq只枚舉了 p 的取值q 始終為默認(rèn) False導(dǎo)致誤判為矛盾式。原因collect_vars只遍歷了左子樹(shù)或者去重時(shí)用了錯(cuò)誤的集合操作。遞歸收集必須左右子樹(shù)都走且用 set 去重。解決在collect_vars里加打印確認(rèn)每個(gè)變?cè)急辉L問(wèn)到?；蛘邔懸粋€(gè)單元測(cè)試對(duì)pqr檢查收集結(jié)果是否為{p,q,r}。4.3 蘊(yùn)含和等價(jià)的真值定義記混現(xiàn)象p-q在pFalse, qFalse時(shí)輸出 False但正確應(yīng)該是 True。原因把蘊(yùn)含當(dāng)成了p and q或者p q。蘊(yùn)含p→q只有在前件真后件假時(shí)為假其余全真。解決在evaluate里把-寫成(not left_val) or right_val把-寫成left_val right_val。用四個(gè)賦值組合逐一驗(yàn)證(F,F)-T、(F,T)-T、(T,F)-F、(T,T)-T。4.4 遞歸下降遇到空輸入或多余括號(hào)現(xiàn)象輸入()或p)時(shí)程序崩潰拋出 IndexError 或無(wú)限遞歸。原因parse_atom遇到)時(shí)沒(méi)有處理consume在 token 耗盡時(shí)返回(None, None)導(dǎo)致后續(xù)判斷出錯(cuò)。解決在parse入口檢查 token 列表是否為空在parse_atom里遇到非 VAR 非 LPAREN 的 token 直接拋異常在consume里如果self.pos len(self.tokens)就拋 ValueError。這樣錯(cuò)誤信息清晰答辯時(shí)也能說(shuō)明健壯性。4.5 剪枝版本在邊界情況下誤判現(xiàn)象某個(gè)公式樸素枚舉是重言式剪枝版本卻返回 False。原因三值邏輯里try_evaluate對(duì)-的處理不完整。比如lNone, rFalse時(shí)p→False等價(jià)于?p結(jié)果取決于 p應(yīng)該返回 None但如果代碼寫成if l is False or r is True: return True然后直接return (not l) or r當(dāng) l 為 None 時(shí)not None是 True整個(gè)返回 True就錯(cuò)了。解決三值邏輯的每個(gè)運(yùn)算符都要顯式處理 None 分支。-的正確邏輯如果 l 是 False 或 r 是 True返回 True如果 l 是 None 或 r 是 None返回 None否則返回(not l) or r。寫完用隨機(jī)公式和樸素枚舉對(duì)照 100 組確保一致。5. 把判別器做成可展示的工具輸出中間結(jié)果與性能對(duì)比課程設(shè)計(jì)答辯時(shí)老師不會(huì)只看“是/否”兩個(gè)答案。你需要展示真值表、表達(dá)式樹(shù)結(jié)構(gòu)、剪枝跳過(guò)的分支數(shù)甚至不同算法的耗時(shí)對(duì)比。這些中間結(jié)果能讓你的報(bào)告厚實(shí)很多也能在答辯時(shí)主動(dòng)引導(dǎo)提問(wèn)方向。先加一個(gè)真值表打印函數(shù)。對(duì) k 個(gè)變?cè)敵?2^k 行每行列出賦值和公式結(jié)果。k 超過(guò) 10 時(shí)只打印前 16 行和后 16 行中間用省略號(hào)避免刷屏。# 打印真值表限制行數(shù) def print_truth_table(node, variables, max_rows32): n len(variables) total 1 n print( | .join(variables) | 結(jié)果) print(- * (len(variables) * 4 6)) for mask in range(total): if total max_rows and max_rows // 2 mask total - max_rows // 2: if mask max_rows // 2: print(...) continue assignment {} for i, var in enumerate(variables): assignment[var] bool((mask i) 1) result evaluate(node, assignment) row | .join(T if assignment[v] else F for v in variables) print(f{row} | {T if result else F})再做一個(gè)表達(dá)式樹(shù)的括號(hào)化輸出把樹(shù)還原成帶括號(hào)的字符串方便檢查解析是否正確。后序遍歷遇到運(yùn)算符就加括號(hào)。# 表達(dá)式樹(shù)轉(zhuǎn)帶括號(hào)字符串 def tree_to_string(node): if node.var: return node.var if node.op !: return f?{tree_to_string(node.left)} left tree_to_string(node.left) right tree_to_string(node.right) return f({left}{node.op}{right})最后加一個(gè)性能對(duì)比表格在報(bào)告里列出不同變?cè)獢?shù)量下樸素枚舉和剪枝版本的耗時(shí)。用time.perf_counter()計(jì)時(shí)每個(gè)規(guī)模跑 3 次取平均。下面是一個(gè)示例表格結(jié)構(gòu)你可以在自己機(jī)器上填真實(shí)數(shù)據(jù)。變?cè)獢?shù)樸素枚舉耗時(shí)(ms)剪枝版本耗時(shí)(ms)剪枝跳過(guò)分支比例812155%1221018018%163400210035%20580002200052%注意剪枝在變?cè)贂r(shí)可能更慢因?yàn)槿蹬袛嘤蓄~外開(kāi)銷。變?cè)獢?shù)超過(guò) 16 后剪枝優(yōu)勢(shì)才明顯。這個(gè)結(jié)論寫進(jìn)報(bào)告比單純說(shuō)“剪枝更快”有說(shuō)服力。還有一個(gè)實(shí)用技巧把公式解析和判別封裝成一個(gè)函數(shù)接收字符串返回結(jié)果和中間數(shù)據(jù)方便批量測(cè)試。# 一站式接口 def check_tautology(formula): tokens tokenize(formula) tree Parser(tokens).parse() vars_set set() collect_vars(tree, vars_set) variables sorted(vars_set) result is_tautology(tree, variables) return { formula: formula, variables: variables, tree: tree_to_string(tree), is_tautology: result, var_count: len(variables) } # 批量測(cè)試 test_formulas [ p|!p, p!p, (p-q)(q-r)-(p-r), (p-q)(q-r)-(p-r), p-(q-p), (pq)-p, p|q-p, ] for f in test_formulas: info check_tautology(f) print(f{info[formula]}: 變?cè)獅info[variables]}, 重言式{info[is_tautology]})跑完這批測(cè)試你會(huì)發(fā)現(xiàn)p|q-p不是重言式因?yàn)閜False, qTrue時(shí)p|q為 True蘊(yùn)含后件 p 為 False整體為 False。這個(gè)反例在答辯時(shí)經(jīng)常被問(wèn)到提前準(zhǔn)備好。我自己的習(xí)慣是每加一個(gè)功能先跑一遍這組固定測(cè)試確認(rèn)沒(méi)有回歸。尤其是改解析器或求值函數(shù)后這組測(cè)試能快速暴露問(wèn)題。課程設(shè)計(jì)代碼量不大但邏輯密度高一個(gè)優(yōu)先級(jí)寫反就能讓全部結(jié)果錯(cuò)位。把測(cè)試用例固化下來(lái)比反復(fù)手動(dòng)輸入公式靠譜得多。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取