簡介這份實驗報告圍繞“算數(shù)表達式求值”課程設(shè)計展開面向正在學習數(shù)據(jù)結(jié)構(gòu)與算法、需要完成棧相關(guān)課程設(shè)計的大中專學生。程序采用算符優(yōu)先法處理含括號的加、減、乘、除混合表達式借助運算符棧oprt、數(shù)字棧num和臨時棧temp完成運算從鍵盤讀入以“#”為邊界的合法表達式輸出計算結(jié)果并顯示輸入序列和棧的變化過程。報告完整介紹了算法設(shè)計思想、運算符優(yōu)先級關(guān)系、核心功能函數(shù)創(chuàng)建棧、出入棧、判空、取棧頂、優(yōu)先級比較、中間計算等、主要流程圖和運行效果截圖還分析了時間與空間復(fù)雜度均為O(n)適合直接對照實現(xiàn)代碼和撰寫報告。文檔額外補充了棧滿動態(tài)擴容、除數(shù)為0、非法輸入、括號不匹配等異常處理說明體現(xiàn)出從“能算”到“可靠”的工程考量。整個資源為1個docx文檔壓縮包大小2.29MB目前已有3620人瀏覽學習可作為課程設(shè)計報告模板、編碼調(diào)試參考及答辯準備材料。1. 算數(shù)表達式求值這門數(shù)據(jù)結(jié)構(gòu)實驗卡住你的不是語法算數(shù)表達式求值是數(shù)據(jù)結(jié)構(gòu)課程里出現(xiàn)頻率最高的一類實驗給一串中綴表達式比如12*3要按運算符優(yōu)先級算出結(jié)果。很多人的程序調(diào)不通問題根本不是語法寫錯而是沒想清楚棧的進出時機——運算符要等優(yōu)先級更高的運算符算完才能出場這個“等待”正是棧存在的意義。這項實驗覆蓋的是線性結(jié)構(gòu)上的狀態(tài)記憶搞懂它之后括號匹配、編譯原理的詞法分析、逆波蘭式計算器都能順手打通。它適合正在寫數(shù)據(jù)結(jié)構(gòu)實驗報告的學生、期末復(fù)習和考研刷題的人以及想補一補棧應(yīng)用的開發(fā)者。本文按實驗報告的順序走先立原理再給可直接編譯的 C 語言實現(xiàn)最后是翻車現(xiàn)場和批量驗證方法。2. 中綴轉(zhuǎn)后綴把人的優(yōu)先級裝進棧里2.1 人讀中綴機器讀后綴兩種表達式的本質(zhì)差異先看兩個式子。中綴表達式12*3人一看就知道先乘后加結(jié)果是 7。但計算機從左讀到右讀到時并不知道后面還有個*在等著。如果直接“見一個運算符算一個”就會算出(12)*39錯了。后綴表達式把運算順序直接寫進排列里1 2 3 * 從頭到尾讀一遍數(shù)字壓棧遇到*彈出兩個數(shù)相乘再壓棧最后遇到彈出兩個數(shù)相加結(jié)果是 7。整個過程中不需要任何優(yōu)先級判斷因為后綴式里*已經(jīng)在前面時機被編碼進了序列。后綴表達式也叫逆波蘭式。它的核心價值是消除了括號和優(yōu)先級的二義性任何中綴式都能無損轉(zhuǎn)成后綴式轉(zhuǎn)換時優(yōu)先級和括號已經(jīng)折算進序列。這就是為什么幾乎所有求值程序都走“中綴轉(zhuǎn)后綴、后綴求值”兩步而不是在中綴上直接加優(yōu)先級邏輯——后者要把優(yōu)先級表嵌進求值循環(huán)邊界情況多到難以收場。實驗報告里常會問“為什么不直接掃描中綴求值”這里給一個可以寫進報告的答案中綴求值必須隨時預(yù)判后續(xù)運算符等效于在掃描過程中維護一個運算符優(yōu)先級棧把這一步拆成顯式的“轉(zhuǎn)后綴”每個階段只做一件事程序可讀性和正確性都顯著更好。這個思想就是編譯原理里詞法分析與語法分析分離的雛形。2.2 運算符優(yōu)先級與棧的進出規(guī)則轉(zhuǎn)后綴的規(guī)則可以濃縮成一張表。設(shè)當前讀到的運算符為 op棧頂為 top當前字符動作數(shù)字直接輸出到后綴式運算符?？栈驐ｍ敒樽罄ㄌ栔苯尤霔＿\算符棧頂優(yōu)先級 當前優(yōu)先級當前入棧運算符棧頂優(yōu)先級 當前優(yōu)先級彈出棧頂輸出重復(fù)比較再把當前入棧左括號直接入棧棧內(nèi)優(yōu)先級視為最低右括號彈棧并輸出直到彈出左括號左括號本身不輸出掃描結(jié)束彈空棧全部輸出優(yōu)先級表最簡單的一版和-同級1*和/同級2。左括號要特殊處理棧內(nèi)優(yōu)先級必須設(shè)得極低比如 0這樣括號后的任何運算符都能壓進去。右括號不參與比較它只負責觸發(fā)“彈到左括號為止”。為什么“棧頂優(yōu)先級 當前”就要彈出因為棧頂那個運算符更“急”它的操作數(shù)已經(jīng)齊了不先算它會破壞優(yōu)先級。拿12*3舉例讀入棧讀 2 輸出讀*時棧頂優(yōu)先級 1 低于*的 2所以*直接入棧讀 3 輸出結(jié)束后先彈*再彈得到1 2 3 * 。換1*23讀*入棧讀時棧頂*優(yōu)先級 2 大等于的 1彈出*輸出入棧得到1 2 * 3 。這一彈一壓就是整個棧邏輯的核心。2.3 括號是作用域不是運算符括號不進入后綴式它只改變運算符的出棧時機。細節(jié)有三個。第一左括號入棧后括號內(nèi)的運算符都要壓在它上面所以左括號的棧內(nèi)優(yōu)先級必須最低否則括號內(nèi)的運算符永遠出不來。第二遇到右括號時不斷彈棧直到彈出左括號如果棧彈空了還沒見到左括號說明右括號多余這是最常見的輸入錯誤。第三括號內(nèi)部按同樣的規(guī)則運行相當于開了一個局部作用域彈到左括號即自動退出——這和函數(shù)調(diào)用棧的返回行為是同一個模型。有一個容易忽略的點每次取棧頂前先判空永遠是這類程序的基本衛(wèi)生習慣。寫代碼時把isOperator、getPriority、pop拆開每個函數(shù)只做一件事調(diào)試時能省大量時間。很多人把左括號當普通運算符入棧最后又把它輸出到后綴式這就是沒理解括號是作用域標記不是運算。2.4 后綴求值一路壓棧遇到運算符再算后綴求值的流程比轉(zhuǎn)換更簡單讀 token數(shù)字壓棧讀到運算符彈出兩個數(shù)先彈出的是右操作數(shù)后彈出的是左操作數(shù)算完把結(jié)果壓回去掃描結(jié)束后棧頂就是答案。以2 3 4 * 為例2、3、4 依次壓棧讀到*彈出 4 和 3算 3*412 壓回讀到彈出 12 和 2算 21214。這里必須記住彈出順序?qū)? 2 -掃描 1 壓棧、2 壓棧讀到-時棧頂是 2先彈出的是b2再彈出a1結(jié)果是a-b-1。寫成apop(); bpop()就會得 1-2 還是 2-1 搞反減法除法全錯。很多人的求值程序翻車都翻在這一行不是算法理解問題是“先彈出的是右操作數(shù)”這個直覺沒建立。轉(zhuǎn)移與求值都是線性掃描中綴轉(zhuǎn)后綴每個字符最多進出棧一次O(n)后綴求值每個 token 進出棧一次O(n)?？傮w時間 O(n)棧深度不超過運算符數(shù)量空間 O(n)。實驗報告里寫“時間 O(n2)”是錯的那只有在彈棧時反復(fù)遍歷棧才會出現(xiàn)。3. 用C語言跑通求值程序完整可抄的實現(xiàn)與報告要點3.1 棧的封裝與表達式讀入我一般用字符串數(shù)組做棧而不是單字符棧。原因很直接后綴式里的數(shù)字可能是多位數(shù)或小數(shù)單個char存不下。用 token 數(shù)組每個元素存一個字符串轉(zhuǎn)換和求值兩個階段都能復(fù)用。#include stdio.h #include stdlib.h #include string.h #include ctype.h #define MAX 100 typedef struct { char data[MAX][MAX]; /* 每個元素存放一個 token運算符或數(shù)字字符串 */ int top; } Stack; void init(Stack *s) { s-top -1; } void push(Stack *s, char *val) { strcpy(s-data[(s-top)], val); } char *pop(Stack *s) { return s-data[(s-top)--]; } char *getTop(Stack *s) { return s-data[s-top]; } int isEmpty(Stack *s) { return s-top -1; } int main() { char expr[MAX], cleaned[MAX]; char postfix[MAX][MAX]; int postfixLen, i, j 0; printf(請輸入表達式: ); fgets(expr, MAX, stdin); /* 去掉空白字符避免空格打斷數(shù)字和運算符的掃描 */ for (i 0; expr[i] ! \0; i) { if (expr[i] ! expr[i] ! \n expr[i] ! \t) cleaned[j] expr[i]; } cleaned[j] \0; infixToPostfix(cleaned, postfix, postfixLen); printf(后綴式: ); for (i 0; i postfixLen; i) printf(%s , postfix[i]); printf(\n); double result evaluatePostfix(postfix, postfixLen); printf(結(jié)果: %g\n, result); return 0; }fgets比gets安全不會越界。清洗階段把空格、換行、制表符全部刪掉后面讀數(shù)字的循環(huán)就不用考慮空白打斷。postfix是二維數(shù)組每一行存一個 tokenpostfixLen記錄 token 總數(shù)。注意MAX是固定上限實驗規(guī)模夠用如果要處理超長表達式改成動態(tài)分配即可。3.2 核心算法一中綴轉(zhuǎn)后綴轉(zhuǎn)換函數(shù)接收清洗后的中綴字符串輸出后綴 token 數(shù)組。優(yōu)先級函數(shù)用switch寫最直白左括號棧內(nèi)優(yōu)先級設(shè)為 0保證比任何運算符都低。int getPriority(char op) { switch (op) { case : case -: return 1; case *: case /: return 2; case (: return 0; /* 左括號在棧內(nèi)優(yōu)先級最低 */ default: return -1; } } int isOperator(char c) { return c || c - || c * || c /; } void infixToPostfix(char *infix, char postfix[][MAX], int *postfixLen) { Stack opStack; init(opStack); int i 0, k 0; while (infix[i] ! \0) { if (isdigit(infix[i]) || infix[i] .) { /* 連續(xù)讀數(shù)字和小數(shù)點形成一個完整 token避免把 12 拆成 1 和 2 */ int start i; while (isdigit(infix[i]) || infix[i] .) i; strncpy(postfix[k], infix start, i - start); postfix[k][i - start] \0; k; continue; } if (infix[i] () { push(opStack, (); } else if (infix[i] )) { /* 彈出運算符直到左括號左括號不輸出 */ while (!isEmpty(opStack) strcmp(getTop(opStack), () ! 0) { strcpy(postfix[k], pop(opStack)); } if (!isEmpty(opStack)) pop(opStack); } else if (isOperator(infix[i])) { char op[2] {infix[i], \0}; /* 棧頂優(yōu)先級 當前先彈出保證乘除先于加減 */ while (!isEmpty(opStack) strcmp(getTop(opStack), () ! 0 getPriority(getTop(opStack)[0]) getPriority(op[0])) { strcpy(postfix[k], pop(opStack)); } push(opStack, op); } i; } /* 全部彈空 */ while (!isEmpty(opStack)) { strcpy(postfix[k], pop(opStack)); } *postfixLen k; }數(shù)字分支里的strncpy從infix start截取一段連續(xù)數(shù)字加小數(shù)點的子串這就是處理多位數(shù)和小數(shù)的關(guān)鍵少了這個循環(huán)123一定會被拆成1、2、3三個 token。運算符分支的while條件寫全三個判斷棧非空、棧頂不是左括號、棧頂優(yōu)先級不低于當前少一個都會出錯。最后收尾彈空棧不能漏否則棧里剩下的運算符全部丟失。提示strncpy不保證目標字符串以\0結(jié)尾所以下一行必須手動寫postfix[k][i - start] \0。這一步漏掉后續(xù)strcmp和printf都會讀到臟數(shù)據(jù)。3.3 核心算法二后綴求值求值棧用double數(shù)組因為運算結(jié)果是浮點數(shù)。遇到數(shù)字就atof轉(zhuǎn)換遇到運算符就彈出兩個數(shù)。double evaluatePostfix(char postfix[][MAX], int len) { double stack[MAX]; int top -1; int i; for (i 0; i len; i) { if (postfix[i][0] 0 postfix[i][0] 9) { stack[top] atof(postfix[i]); } else { double b stack[top--]; /* 先彈出右操作數(shù) */ double a stack[top--]; /* 再彈出左操作數(shù) */ switch (postfix[i][0]) { case : stack[top] a b; break; case -: stack[top] a - b; break; case *: stack[top] a * b; break; case /: if (b 0) { printf(除零錯誤\n); exit(1); } stack[top] a / b; break; } } } return stack[top]; }postfix[i][0]判斷首字符是數(shù)字還是運算符能覆蓋正數(shù)情況。負數(shù)目前不支持第 4 章會專門講。bstack[top--]先取到的是棧頂也就是后壓入的數(shù)運算順序必須保持a-b、a/b。除零分支用exit(1)直接退出比返回一個特殊值更干凈至少不會帶著inf繼續(xù)算。3.4 實驗報告的結(jié)構(gòu)與測試用例表報告骨架一般按這個順序?qū)憜栴}描述、數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法描述、核心代碼、測試、復(fù)雜度分析、總結(jié)。老師看報告時重點看兩處數(shù)據(jù)結(jié)構(gòu)為什么選棧以及測試用例有沒有覆蓋邊界。選棧的理由要寫“運算符的延遲運算與棧的后進先出語義一致”不要只寫“用棧實現(xiàn)”。測試表格建議做成這樣每個用例標注覆蓋點輸入后綴式輸出覆蓋點121 2 3基本加法12*31 2 3 * 7運算符優(yōu)先級(12)*31 2 3 *9括號改變優(yōu)先級2*(34)/52 3 4 * 5 /2.8混合運算與除法12.5-3.512.5 3.5 -9多位數(shù)與小數(shù)復(fù)雜度分析寫 O(n) 時間、O(n) 空間并說明為什么是線性每個字符最多入棧出棧各一次。加上除零檢測和括號匹配失敗檢測報告里可以明確寫“程序?qū)Ψ欠ㄝ斎胱隽朔烙詸z查”這會比只跑通 12 的實驗高一個檔次。4. 求值程序最容易翻車的5個坑現(xiàn)象、原因與處理4.1 多位數(shù)和小數(shù)被拆成單字符現(xiàn)象輸入123結(jié)果算出 5或者后綴式變成1 2 3 。原因逐字符處理數(shù)字時遇到一個數(shù)字立刻輸出一個 token沒有把連續(xù)的數(shù)字串讀完整。isdigit(infix[i])只判斷當前字符不負責“聚攏”它后面的數(shù)字。解決在數(shù)字分支里用while (isdigit(infix[i]) || infix[i] .) i;一直讀到數(shù)字串末尾再用strncpy截取完整 token。第 3 章代碼已經(jīng)是這個寫法但很多人會把它簡化成單字符輸出這是后綴式錯亂的第一個源頭。4.2 括號匹配失敗導(dǎo)致棧操作越界現(xiàn)象輸入(12*3程序崩潰或輸出亂碼輸入12)彈棧彈到空棧。原因右括號處理時沒有判棧空直接無限彈棧直到越界左括號多余時最后收尾彈棧把空棧也彈了一遍data[--top]訪問到非法下標。解決右括號的while循環(huán)里加!isEmpty條件彈出的左括號要單獨pop一次不要輸出到后綴式最后收尾彈棧前判空。更穩(wěn)妥的做法是掃描開始時先做一遍括號匹配預(yù)檢左右括號數(shù)量一旦不相等直接報錯退出不進入后續(xù)邏輯。4.3 減法、除法把操作數(shù)順序?qū)懛船F(xiàn)象2-3算出 18/4算出 0.25乘法和加法卻正常。原因后綴求值時先彈出的是棧頂也就是表達式里靠后的數(shù)它是右操作數(shù)后彈出的是左操作數(shù)。寫了apop(); bpop()就全反了。解決固定寫成double b stack[top--]; double a stack[top--];再做a-b、a/b。這一條幾乎每個做求值實驗的人都踩過我當年也翻過一次車后來每次寫棧相關(guān)代碼都會先默念一遍“先出棧的是右操作數(shù)”。4.4 除零沒有顯式處理現(xiàn)象8/0在部分環(huán)境直接浮點異常崩潰在另一些環(huán)境輸出inf后續(xù)判斷產(chǎn)生臟數(shù)據(jù)。原因C 語言對除以 0 的行為依賴運行時double除法在 IEEE 754 下可能給inf整數(shù)除法或某些編譯環(huán)境直接崩。解決在除法分支顯式檢查if (b 0)打印錯誤并退出。實驗報告里把“除零檢測”寫成獨立函數(shù)或一個判斷分支屬于加分項。不要依賴平臺的默認行為那是玄學不是程序邏輯。4.5 負數(shù)和空格讀入階段被忽略的細節(jié)現(xiàn)象-32解析失敗或者帶空格的1 2把數(shù)字拆成多個 token。原因一元負號缺少處理空格沒有在預(yù)處理階段剔除isdigit的連續(xù)讀數(shù)字循環(huán)遇到空格就斷開了。解決讀入階段把所有空格、換行、制表符全部刪掉這是最簡單的止血方案。一元負號的處理方式是預(yù)處理把開頭的-和左括號后面的-替換成0-比如-32變成0-32(-32)變成(0-32)。替換后完全復(fù)用現(xiàn)有算法不用動求值核心。這個方案在實驗報告里寫清楚比硬撐一個負號狀態(tài)機更可靠。4.6 用 printf 大法定位棧狀態(tài)現(xiàn)象結(jié)果不對但看不出是在轉(zhuǎn)換階段錯還是求值階段錯。原因棧是黑匣子中間狀態(tài)不可視化靠肉眼盯著代碼很難定位。解決在push和pop的位置各加一行fprintf(stderr, push/pop: %s, top%d\n, val, s-top);跑一遍12*3對比棧里運算符的進出順序是否符合 2.2 節(jié)的規(guī)則。定位到具體字符后把調(diào)試輸出刪掉即可。調(diào)試棧程序的技巧永遠是“看它的進出序列”而不是猜。5. 批量自測與變量擴展給你的實驗報告加點分量5.1 用腳本批量驗證正確性手動輸入幾個用例很難覆蓋所有邊界我一般會寫一個 Python 腳本隨機生成表達式把 C 程序的輸出和 Python 的eval結(jié)果比對。import subprocess import random ops [, -, *, /] def gen_expr(): n random.randint(2, 4) expr str(random.randint(1, 20)) for _ in range(n): expr random.choice(ops) str(random.randint(1, 20)) return expr for _ in range(100): expr .join(gen_expr()) # 故意加空格測試清洗邏輯 out subprocess.run([./calc], inputexpr \n, capture_outputTrue, textTrue) got float(out.stdout.strip().split(結(jié)果: )[1]) expected eval(expr.replace( , )) if abs(got - expected) 1e-6: print(不匹配:, expr, got, expected) break else: print(100 條全部通過)腳本把隨機生成的式子通過管道喂給編譯好的calc程序再對比輸出。生成的表達式故意帶空格是為了連預(yù)處理邏輯一起測。eval只用來做測試參照不參與 C 程序的實現(xiàn)。跑通 100 條隨機用例后把測試結(jié)果截圖放進報告比只寫“測試通過”更有說服力。5.2 變量替換讓表達式支持字母進階實驗最常見的要求是支持變量比如ab*c進入求值前先給a、b、c賦值。常見做法是在讀入后做一次字符替換遍歷輸入遇到a就替換成對應(yīng)的數(shù)字字符串替換完再交給中綴轉(zhuǎn)后綴。替換表用一個簡單的結(jié)構(gòu)體數(shù)組就夠了兩三個變量用if都可以。這個擴展不需要改動轉(zhuǎn)換和求值核心卻能讓實驗報告多出一節(jié)“擴展功能”在答辯或驗收時是個不錯的亮點。我做這個實驗時中綴轉(zhuǎn)后綴寫了三版才完全跑通最后發(fā)現(xiàn)所有 bug 都集中在 4.3 提到的順序問題上。從那以后我養(yǎng)成了習慣寫棧程序先列測試用例再動手寫邏輯不急著敲代碼。這個習慣幫我避開了后面不少坑也希望幫到你。本文還有配套的精品資源點擊獲取