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