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