資料結構課程設計報告書

南通大學計算機學院

題目： 2.3表示式求值問題

專業：電腦科學與技術

開始日期： 2013.01.14

完成日期： 2012.01.16

表示式是資料運算的基本形式。人們的書寫習慣是中綴式，如：11+22*（7-4）/3。

中綴式的計算按運算子的優先順序及括號優先的原則，相同級別從左到右進行計算。表示式還有字尾式（如：22 7 4 - * 3 / 11 +）和字首式（如：

+ 11 / * 22 – 7 4 3）。字尾表示式和字首表示式中沒有括號，給計算帶來方便。如字尾式計算時按運算子出現的先後進行計算。

本設計的主要任務是進行表示式形式的轉換及不同形式的表示式計算。

選擇了棧，在某些運算部分採用了陣列。

重點是棧的使用問題，棧是限制只能在表的一端進行插入和刪除的線性表，棧頂能進行插入和刪除而棧底不允許插入和刪除。

難點是使用棧存表示式和讓表示式逆序輸出這些問題。

圖2-1 系統模組圖

要求：描述系統所採用資料結構的抽象資料型別，只要說清楚資料物件、資料關係，基本操作集合，切勿複製大量**，可以參考教材如何定義adt的。例如：

adt stack

資料關係:r=

3.1.1 adt操作

（1）char precede(char t1,char t2)

進行運算子優先順序的比較

括號優先順序高，其實乘除，最後加減

（5） int in(char c)

判斷輸入的c是否是運算子

（6） double operate(double a,char theta,double b)

進行一次運算

進行加減乘除運算

（7） double val_exp(char *exp)

進行中綴表示式的求值

step 1：設定兩棧，操作符棧和運算元棧；

step 2：棧初始化：設運算元棧為空；

step 3：依次讀入字元：若是運算元則入棧；

如果是操作符：

若優先順序小於棧頂元素，則退棧、計算，結果壓入運算元棧；

若優先順序等於棧頂元素，則脫括號；

若優先順序大於棧頂元素，則壓入操作符棧；

（5） void createpostexp(char * exp,char * &postexp)

中綴表示式求字尾表示式

step 1：設立暫存運算子的棧；

step 2：設表示式的結束符為「=」；

step 3：若當前字元是運算元，則直接給輸出串；

step 4：若當前運算子的優先順序高於棧頂運算子，則壓棧；

step 5：否則，棧頂運算子出棧；

step 6：「（」對它之前後的運算子起隔離作用，「）」可視為自相應左右括弧的表示式的結束符。

（6）double val_postexp(char *postexp)

字尾表示式求值

step 1:讀入表示式的乙個字元；

step 2：若是運算元，壓入棧，轉4；

step 3：若是運算子，從棧中彈出兩個數，將運算結果壓入棧

step 4：若表示式輸入完畢，棧頂即表示式值；

若表示式未輸入完，轉1；

（7）void createprefax(char * exp,char * &prefax)

中綴表示式求字首表示式

step 1：求輸入串的逆序；

step 2：檢查輸入的下乙個元素；

step 3：假如是運算元，把他新增到輸出串；

step 4：假如是閉括號，將它壓棧；

step 5：假如是運算子，則：

（1）如果棧空，此運算子入棧；

（2）如果棧頂是閉括號，此運算子入棧；

（3）如果它的優先順序高於或等於棧頂運算子，此運算子入棧；

（4）否則，棧頂運算子出棧並新增到到輸出串，重複步驟5；

step 6：假如是開括號，棧中運算子逐個出棧並輸出，知道遇到閉括號，閉括號出棧並丟棄；

step 7：假如輸入還未完畢，跳轉到步驟2；

step 8：假如輸入完畢，棧中剩餘所有元素操作符出棧並加到輸出串中；

step 9：求輸出串的逆序。

（8）double va2_prefax(char *prefax)

字首表示式求值

step 1：從左到右掃瞄字首表示式；

step 2：從右面的第乙個字元開始判斷：

（1）：如果該字元時運算元，則一直到數字串的末尾再記錄下來；

（2）：如果是運算子，則將右邊離得最近的兩個「數字串」作相應的運算，以此作為乙個新的數字串並記錄下來，一直掃瞄到表示式的最左端時，最後運算的值也就是表示式的值。

3.2.1 登入/錄入模組

（1）介面設計

（2）處理流程設計

執行：0錯誤，0警告；

測試：以下四個圖為測試結果：

圖（1）：表示式的建立和表示式的求值；

圖（2）：求字尾表示式和字尾表示式求值；

圖（3）：求字首表示式和字首表示式求值；

圖（4）：顯示表示式和退出系統

整個表示式求值程式過程中出現了不少問題。比如在整個程式中使用float造成了多警告，在改用double後得到解決；在求字首表示式的問題中，用定義的字元去表示棧頂操作符和優先順序比較的大小值，也造成了程式雖無錯但無法執行的情況，最終直接用op.gettop()和呼叫了優先順序比較函式解決了問題；在字首表示式求值部分，出現了考慮不周的情形，比如把帶小數的中綴表示式輸入後執行出的結果錯誤，問題出在表示式出棧時小數的小數點左右的兩個數字調換了，經過思考發現需要對輸出的小數採用一次逆輸出才解決了問題。

除錯過程還出現了if與else if 不配對的問題，但都通過思考和請教別人解決了。

這次的課程設計比大一兩學期的課程設計都來的綜合，讓我認識到了自己很多方面知識的缺漏，讓我在使用c++語言解決問題方面得到了鍛鍊，也清楚的意識到了自己能力的欠缺，比如不會使用qt進行介面設計，需要自己去自學。在編寫程式的過程中，思路的清晰是最重要的，其次就是編寫時要謹慎，要細心。而在除錯過程中，堅持很重要，除錯是個複雜的過程，需要一次次去修改錯誤，我們不能放棄。

另外，請教他人也是不可少的，因為在長時間的除錯過程中，我們容易產生固定思維，此時讓別人幫忙看看錯誤也許更容易發現。以上，就是我對本次課程設計一些體會和總結。

//附錄

源程式：

#include//cout,cin

#include"process.h"//exit()

#include"stdio.h"//eof,null

#include

#include // atoi()

#include"sqstack.h"

char pause;

char precede(char t1,char t2)

{//算符的優先順序比較

char f;

switch(t2)

{case '+':

case '-':if(t1=='('||t1=='=')

f='<';

else

f='>';

break;

case '*':

case '/':if(t1=='*'||t1=='/'||t1==')')

f='>';

else

f='<';

break;

case '(':if(t1==')')

cout<<"error1"

else

f='<';

break;

case ')':switch(t1)

case '(':f='=';

break;

case '=':cout<<"error2"

default: f='>';

break;

case '=':switch(t1)

資料結構課程設計報告書

資料結構課程設計報告書

資料結構課程設計報告

資料結構課程設計報告

相關推薦