數據結構實驗報告總結

設計題目：模擬計算器程序

學生姓名：謝先斌

系 別：計算機與通信工程學院

專 業：計算機科學與技術

班 級：1班

學 號：541007010144

指導教師：盧冰 李曄

2012 年 6 月 21 日

鄭州輕工業學院

課 程 設 計 任 務 書

題目 模擬計算器程序

專業、班級 計算機科學與技術10-01班 學號 541007010144 姓名 謝先斌

主要內容：

設計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運算符及SQR和ABS函數的任意整型表達式進行求解。

基本要求：

要檢查有關運算的條件，並對錯誤的條件產生報警。

主要參考資料：

[1] 嚴蔚敏 吳偉民 編著《數據結構(C語言版)》 清華大學出版社 第44頁 3.1 棧、第52頁3.2.5表達式求值

完 成 期 限： 2012年6月21日

指導教師簽名：

課程負責人簽名：

2012年 6月 21 日

一、 設計題目

模擬計算器的程序

設計一個模擬計算器的程序，要求能對包含加、減、乘、除、括號運算符及SQR和ABS函數的任意整型表達式進行求解。

設計要求：要檢查有關運算的條件，並對錯誤的條件產生報警。

二、 算法設計的思想

本程序設計主要是應用了棧，利用棧的“先進後出”原理，建立了兩個棧，分別爲運算符棧pOStack和運算數棧pDStack。算法的基本思想(參考課本p53頁)是：

(1) 首先置操作數棧爲pDStack空棧，表達式起始符爲“=”，位運算符棧的棧底元素;

(2) 依次讀入表達式中的每個字符，若是操作數則進入pDStack棧，若是運算符則和pOStack棧的棧定運算符比較優先權後作相應操作，直到整個表達式求值完畢(即pOStack棧的棧定元素和當前讀入的字符均爲“=” )。

三、 算法的流程圖

本程序的流程如下附圖1所示：

附圖1 程序流程圖

四、 算法設計分析

首先創建了兩個棧：

typedef struct OPStack //定義運算符棧

{

char opStack[MAX_OPERATOR_NUM];

int top;

}OPStack, *pOPStack;

typedef struct DATAStack //定義運算數棧

{

double stack[MAX_DATA_NUM];

int top;

}DATAStack, *pDATAStack;

來分別存放運算符和運算數。在兩個結構體中均有一個top數據域，當top=-1時，表示該站爲空棧。

定義一個Evaluateexpression_r()函數來完成函數運算的主要功能：讀入表達式，並計算結果。以下是對該函數的分析：

當一次運算開始時，分別調用InitpOPStack(pOPStack &pOStack)函數和InitpDATAStack(pDATAStack &pDStack)函數分別對運算符棧和運算數棧進行初始化。調用PushOPStack(pOStack, '=')函數來完成運算符棧棧低元素的設置。

通過PushOPStack(pOPStack &pOStack, char ch)函數、

PopOPStack(pOPStack &pOStack, char &ch)函數、

PushDATAStack(pDATAStack &pDStack, double d)函數和PopDATAStack(pDATAStack &pDStack, double &d)函數來分別完成運算符和運輸數的進出棧操作。getToppOPStack(pOPStack &pOStack)函數和getToppDATAStack(pDATAStack &pDStack) 函數主要是進行得到棧定元素的作用，特別是在對運算符棧優先級的.比較中十分重要，其中還會調用IsOP(char &ch) 函數來區分讀入的是運算符還是運算數。

ChangeChar(char &c)函數當每次讀入一個字符是都會調用一次，主要的作用就是完成不用區分A、S的大小的功能。

Precede(char op1, char op2)函數主要是通過一個二維字符串數組來存放9種運算符的優先級比較的結果，每當讀到一個運算符後就進行與運算符棧頂元素比較，通過返回的“<、>、=”結果來進行下一步的操作：'<'表示棧頂元素優先級低，運算符進棧;'='表示脫括號並接受下一個字符;'>'表示運算符和運算數各退棧一次並調用Operate(double a, char theta, double b)函數(主要是對出棧的運算符和運算數進行計算)，最後將運算結果壓入運算數棧pDStack。

當操作結束時運算數棧的棧頂元素就是計算結果，分別調用ClearpOPStack(pOStack)函數清空運算符棧、ClearpDATAStack(pDStack)函數清空運算數棧以待下一次繼續進行相關操作。

print_user()函數和exit_E()函數開始和結束時個調用一次，分別完成歡迎界面和退出界面的佈置。main()是本程序的主函數，主要通過while語句和switch語句來完成本程序的運行，當輸入Y(y)時調用Evaluateexpression_r()函數完成計算，當輸入N(n)時，調用exit_E()函數退出本程序的運行。

本程序還考慮到各種異常的處理，如運算時除數爲0、被開方數爲0等情況的出現，最終的處理是直接退出程序的運行。

五、 運行結果分析

1. 程序開始界面，如附圖2：

附圖2 開始界面

2.如下附圖3，附圖4分別是選擇進入和退出程序界面：

附圖3(在以下界面輸入計算式即可運行出計算結果如附圖5)

附圖4 退出界面

附圖5 運行界面

2. 對異常的處理

a) 對異常1除數爲0，如輸入“1+2/0=”程序將直接退出，如附圖6：

附圖6 異常1除數爲0

b) 對異常2被開方數爲負數，如輸入“3+S(-9)=”程序將直接退出，如附圖7：

附圖7 異常2被開方數爲負數

3.以下是對各種簡單運算的運行結果，如附圖8：

附圖8 簡單運算

3. 綜合運算：如式子“1/2+A(7-8)-S(9*8)=”運行結果如附圖9

附圖9 綜合運算

六、 收穫及體會

本程序以C語言的棧的相關知識爲基礎，通過控制兩個棧(運算數棧和運算符棧)的進出的棧操作，來實現對包含加、減、乘、除、括號運算符及SQRT和ABS函數的任意整型表達式的求解運算。

從程序的編寫來看，感覺這次自己真的學到了好多，特別是對程序的開發流程。從最初的選定程序，到最終的程序運行成功，讓我感到如果是僅僅掌握課本上的知識是遠遠不能夠很好的應用到實際的編程中去的。在這個過程中還需要我們更多的去考慮到實際條件的種種限制和約束。

我在寫本程序的過程中也遇到了很多的問題，當然本程序的核心問題就是對兩個棧的壓出棧操作，需要做優先級判斷，並要考慮什麼時候進棧，什麼時候出棧等操作。我採用了課本上第52-54頁講的通過一個二維字符串數組來控制比較“+-*、()AS=”共9個運算符的優先級控制。對異常，如除數爲0、被開方數小於0等異常也進行了精心的處理。對操作過程中要用到的Y、N、A、S等字符也進行了改進，最終本程序可以不區分大小寫就完成相關操作。

總之，經過本次專業課程設計，讓我掌握了開發應用軟件的基本流程，運用所學編程技能的基本技巧，也讓我初步瞭解了軟件設計的基本方法，提高進行工程設計的基本技能及分析、解決實際問題的能力，爲以後畢業設計和工程實踐等打下良好的基礎。相信通過這次的課程設計，我對所學的《數據結構(C語言版)》和各種編程語言都有了一個全新的認識。我也會積極吸取本次課程設計的經驗，繼續研究數據結構和所學的各種編程語言。

七、 源代碼

# include

# include

# include

# include

# define MAX_OPERATOR_NUM 100 //運算符棧數組長度

# define MAX_DATA_NUM 100 //運算數棧數組長度

typedef struct OPStack //定義運算符棧

{

char opStack[MAX_OPERATOR_NUM];

int top;

}OPStack, *pOPStack;

typedef struct DATAStack //定義運算數棧

{

double stack[MAX_DATA_NUM];

int top;

}DATAStack, *pDATAStack;

void InitpOPStack(pOPStack &pOStack) //初始化運算符棧

{

if( !(pOStack = (pOPStack)malloc(sizeof(OPStack)))) //爲運算符棧分配空間

{

printf("分配內存空間失敗! ");

exit(-1);

}

pOStack->top = -1;

}

void InitpDATAStack(pDATAStack &pDStack) //初始化運算數棧

{

if( !(pDStack = (pDATAStack)malloc(sizeof(DATAStack)))) //爲運算數棧分配空間

{

printf("分配內存空間失敗! ");

exit(-1);

}

pDStack->top = -1;

}

void PushOPStack(pOPStack &pOStack, char ch) //運算符進棧

{

pOStack->opStack[++(pOStack->top)] = ch;

}

void PopOPStack(pOPStack &pOStack, char &ch) //運算符出棧

{

ch = pOStack->opStack[pOStack->top];

pOStack->top--;

}

void PushDATAStack(pDATAStack &pDStack, double d) //運算數進棧

{

++(pDStack->top);

pDStack->stack[pDStack->top] = d;

}

void PopDATAStack(pDATAStack &pDStack, double &d) //運算數出棧

{

d = pDStack->stack[pDStack->top];

pDStack->top--;

}

void ClearpOPStack(pOPStack &pOStack) //清空運算符棧

{

pOStack->top = -1;

}

void ClearpDATAStack(pDATAStack &pDStack) //清空運算數棧

{

pDStack->top = -1;

}

char GetToppOPStack(pOPStack &pOStack) //獲取運算符棧頂元素

{

return pOStack->opStack[pOStack->top];

}

double GetToppDATAStack(pDATAStack &pDStack) //獲取運算數棧頂元素

{

return pDStack->stack[pDStack->top];

}

bool IsOP(char &ch) //區分 運算符 和 運算數 的函數，是運算符時返回true,否則返回false

{ //判斷是否爲符號

if ( (ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '=') || (ch == 'A') || (ch == 'S') || (ch == 'a') || (ch == 's') || (ch == '(') || (ch == ')') )

return true;

else

return false;

}

char Precede(char op1, char op2) //參考《數據結構》(C語言版)第53頁 3.2.5表達式求值 表 3.1

{

char tab[9][10]; //定義字符串的二維數組來存放運算符優先級的關係

strcpy( tab[0], ">><<<><<>" );

strcpy( tab[1], ">><<<><<>" );

strcpy( tab[2], ">>>><><<>" );

strcpy( tab[3], ">>>><><<>" );

strcpy( tab[4], "<<<<<=<

strcpy( tab[5], ">>>>E>>>>" );

strcpy( tab[6], ">>>><>>>>" );

strcpy( tab[7], ">>>><>>>>" );

strcpy( tab[8], "<<<<

printf(" | ***歡迎您的下次使用!謝謝!!!*** | "); //退出使用

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

}

double Operate(double a, char theta, double b) //對出棧的運算符和運算數進行計算

{

double s;

switch(theta)

{

case '+':

s = a + b;

break;

case '-':

s = a - b;

break;

case '*':

s = a * b;

break;

case '/':

if ( b != 0 ) //判斷除數是否爲0，若爲0，退出程序

{

s = a/b;

break;

}

else

{

printf(" #### 除數爲0，非法運算。程序終止! #### ");

exit_E(); //打印結束菜單

exit(-1);

}

case 'A':

s = fabs(b); //調用FABS()函數

break;

case 'S':

if( b >= 0) //判斷被開方數是否爲0，若爲0，退出程序

{

s = sqrt(b); //調用SQRT()函數

break;

}

else

{

printf(" #### 求負數的平方根是非法運算。程序終止! #### ");

exit_E(); //打印結束菜單

exit(-1);

}

}

return s;

}

char ChangeChar(char &c) //通過ChangeChar函數來把a、s的小寫字母改爲大寫的

{

if( c == 'a' )

c = 'A';

else if( c == 's' )

c = 'S';

return c;

}

//參考《數據結構》(C語言版)第53頁 3.2.5表達式求值算法3.4 Evaluateexpression_r()函數

void Evaluateexpression_r() //計算函數：讀入表達式，並計算結果

{

pOPStack pOStack; //聲明運算符棧

pDATAStack pDStack; //聲明運算數棧

double result; //存運算的結果

char x, theta, c; //c存放讀取的字符,x、theta存放運算符棧的棧頂元素

int flag, data; //標識符，用來讀入連續的數字

double s;

double getd; //存放GetTop***的結果

double a, b, cc; //a,b存放數據棧出棧的棧頂元素, c存放運算結果

flag = 0; //初始化標識符，用來判斷字符串中的連續數字

data = 0; //

InitpOPStack(pOStack); //初始化運算符棧

InitpDATAStack(pDStack); //初始化運算數棧

PushOPStack(pOStack, '='); //在運算符棧底放入'='

printf(" &請輸入表達式以'='結束：");

c = get); //讀入字符

ChangeChar(c); //通過調用函數來實現把小寫的a、s改爲大寫的A、S

while( c != '=' || GetToppOPStack(pOStack) != '=')

{

if( !IsOP(c) ) //不是運算符進棧

{

s = c - '0'; //把字符轉化爲數字

if ( flag == 1 )

{

PopDATAStack(pDStack, getd);

s = getd*10 + s;

}

PushDATAStack(pDStack, s);

flag = 1;

c = get);

ChangeChar(c);

}

else

{

flag = 0;

switch( Precede(GetToppOPStack(pOStack), c) ) //輸入元素和運算符棧頂元素比較

{

case '<': //棧頂元素優先級低

PushOPStack(pOStack, c);

c = get);

ChangeChar(c);

break;

case '=': //託括號並接受下一個字符

PopOPStack(pOStack, x);

c = get);

ChangeChar(c);

break;

case '>': //退棧並將運算結果進棧

PopOPStack(pOStack, theta);

PopDATAStack(pDStack, b);

PopDATAStack(pDStack, a);

cc = Operate(a, theta, b);

PushDATAStack(pDStack, cc);

break;

}//switch

}//else

}//while

result = GetToppDATAStack(pDStack); //運算結束時，運算數棧的棧底元素就是計算結果

ClearpOPStack(pOStack); //清空運算符棧

ClearpDATAStack(pDStack); //清空運算數棧

printf(" ->計算結果爲：%.2f ", result); //輸出運算結果

return ;

}

void print_user() //歡迎界面

{

printf(" 歡迎使用C語言版模擬計算器 ");

printf("************************************************************************ ");

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

printf(" | 模擬計算器使用說明 | ");

printf(" | 作者：謝先斌 | ");

printf(" | 本程序包括對'+'、'-'、'*'、'/'、'()'的運算 | ");

printf(" | 本程序中ABS()算用A()替代、SQRT()運算用S()代替 | ");

printf(" | 本程序中的一切字母均不區分大小寫 | ");

printf(" 正確的表達式如：1+A(7-8)+S(9*8)= ");

printf(" | 輸入'='表示表達式輸入結束!! | ");

printf(" | 歡迎使用!!!-->--> | ");

printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ");

printf("************************************************************************ ");

}

int main() //主函數

{

char in;

bool b; //標識符，用來標識是否結束程序

b = true; //初始化，不結束

print_user(); //打印歡迎界面

printf(" *請確認使用計算器Y/N:");

while(1)

{

scanf("%c", &in); //確認是否繼續操作

get); //吃掉會車，避免干擾

switch(in)

{

case 'Y':

case 'y':

{

Evaluateexpression_r(); //進入計算函數：讀入表達式，並計算結果

break;

}

case 'N':

case 'n':

{

exit_E();

b = false;

break;

}

//default:

// printf(" **輸入錯誤，請重新輸入Y/N:");

// break;

}

if(b==false) //如果 b==false ,退出整個程序

break;

printf(" *您確定要繼續使用計算機Y/N:");

get); //用getchar吃掉回車，避免對後續輸入中in的干擾

}

return 0;

}