資料結構實驗報告總結
設計題目：模擬計算器程式
學生姓名：謝先斌
系 別：計算機與通訊工程學院
專 業：計算機科學與技術
班 級：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;
}