四川大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)報(bào)告 帶括號(hào)的算術(shù)表達(dá)式

1、鍵入文字鍵入文字鍵入文字?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)報(bào)告課題名稱： 帶括號(hào)的算數(shù)表達(dá)式求值 課題設(shè)計(jì)人（學(xué)號(hào)）： 指導(dǎo)教師： 朱宏評(píng)閱成績(jī)： 評(píng)閱意見： 提交報(bào)告時(shí)間：2014 年 12月 9日帶括號(hào)的算數(shù)表達(dá)式求值計(jì)算機(jī)類 專業(yè)學(xué)生 指導(dǎo)老師 朱宏 摘要 在平時(shí)的生活中，我們可以解決一些簡(jiǎn)單的算術(shù)表達(dá)式，如果當(dāng)我們遇到一些式子較為冗長(zhǎng)，運(yùn)算比較復(fù)雜的算術(shù)表達(dá)式時(shí)，我們都會(huì)選擇計(jì)算器。那么，計(jì)算器又是通過怎樣的原理來進(jìn)行運(yùn)算的呢。本程序利用堆棧先進(jìn)后出的特點(diǎn)，采用操作數(shù)和操作符兩個(gè)堆棧，實(shí)現(xiàn)由中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換并求值的過程。帶括號(hào)的算術(shù)表達(dá)式的求值是堆棧的一個(gè)典型的應(yīng)用實(shí)例。 關(guān)鍵詞：

2、計(jì)算器 堆棧 C+一、實(shí)驗(yàn)名稱:帶括號(hào)的算術(shù)表達(dá)式求值 二、實(shí)驗(yàn)的目的和要求: 1.采用算符優(yōu)先數(shù)算法,能正確求值表達(dá)式; 2.熟練掌握棧的應(yīng)用; 3.熟練掌握計(jì)算機(jī)系統(tǒng)的基本操作方法,了解如何編輯、編譯、鏈接和運(yùn)行一個(gè)C+程序; 4.上機(jī)調(diào)試程序,掌握查錯(cuò)、排錯(cuò)使程序能正確運(yùn)行。三、實(shí)驗(yàn)的環(huán)境：硬件環(huán)境：處理器：Inter(R) Core(TM) i7-4500U內(nèi)存：8.00GB軟件環(huán)境：操作系統(tǒng)：Windows8.1編譯軟件：Microsoft Visual Studio 2012四、算法描述:我設(shè)計(jì)的帶有括號(hào)的算術(shù)表達(dá)式求值的程序中，運(yùn)

3、算符的優(yōu)先級(jí)是這樣子的：1. 先乘除，后加減2. 同級(jí)運(yùn)算從左到右依次運(yùn)算。3. 先括號(hào)內(nèi)的運(yùn)算，再括號(hào)外的運(yùn)算。我的設(shè)計(jì)思路是，先輸入一個(gè)最后不帶等于號(hào)的中綴表達(dá)式，先對(duì)表達(dá)式檢查是否有錯(cuò)誤，如果有將會(huì)輸出“表達(dá)式有錯(cuò)誤”，否則通過堆棧方法將這個(gè)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，然后將后綴表達(dá)式求值。開始程序輸入一個(gè)表達(dá)式檢查表達(dá)式是否有錯(cuò)誤沒有錯(cuò)誤是有錯(cuò)轉(zhuǎn)化為后綴表達(dá)式計(jì)算求值輸出結(jié)果輸出“表達(dá)式有錯(cuò)”是否繼續(xù)否退出程序函數(shù)清單：transform()用于將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式calculate()將后綴表達(dá)式進(jìn)行求值examine()檢查輸入的表達(dá)式是否有錯(cuò)誤main()主程序。五：源程

4、序清單：#include <iostream>#include <cmath>#include <stack>#include <string>using namespace std;string transform(string str)/轉(zhuǎn)換為后綴表達(dá)式stack<char> ope;int i;string exp=""for(i=0;i<int(str.size();i+)if(stri='.'|isdigit(stri)exp+=stri;else if(stri='+

5、9;|stri='-')int j=i-1;if(isdigit(strj)exp+=" "/每個(gè)數(shù)字的后面都加一個(gè)空格加以區(qū)分if(ope.empty()|ope.top()='(')ope.push(stri);elsewhile(!ope.empty()&&ope.top()!='(')exp+=ope.top();ope.pop();ope.push(stri);elseif(ope.empty()|ope.top()='(')ope.push(stri);elsewhile(!ope.

6、empty()&&ope.top()!='(')exp+=ope.top();ope.pop();ope.push(stri);else if(stri='*'|stri='/'|stri='%') int j=i-1;if(isdigit(strj)exp+=" "if(ope.empty()|ope.top()='('|ope.top()='+'|ope.top()='-') ope.push(stri); else while(!ope.em

7、pty()&&ope.top()!='('&&ope.top()!='+'&&ope.top()!='-') exp+=ope.top();ope.pop(); ope.push(stri); elseif(ope.empty()|ope.top()='('|ope.top()='+'|ope.top()='-')ope.push(stri);elsewhile(!ope.empty()&&ope.top()!='('&

8、amp;&ope.top()!='+'&&ope.top()!='-')exp+=ope.top();ope.pop();ope.push(stri);/else if(stri='')int j=i-1;if(strj!=')')exp+=" "ope.push(stri);else if(stri='(')ope.push(stri);else if(stri=')')exp+=" "while(ope.top()!='(&

9、#39;)exp+=ope.top();ope.pop();ope.pop();elsereturn "有錯(cuò)誤"while(!ope.empty()/遍歷完表達(dá)式將堆棧中的所有運(yùn)算符輸出 if(isdigit(expexp.length()-1)exp=exp+" "+ope.top(); ope.pop(); else exp=exp+ope.top(); ope.pop();return exp;int examine(string str)/檢查輸入的表達(dá)式是否有誤if(isdigit(strstr.length()-1)!=0|strstr.le

10、ngth()-1=')')&&(isdigit(str0)!=0|str0='+'|str0='-'|str0='(')int i;for(i=0;i<int(str.length();i+)if(stri='/'|stri='%'|stri='*'|stri='') int a=i+1; if(stra='/'|stra='*'|stra='%'|stra=')'|stra=

11、9;.')cout<<"表達(dá)式有錯(cuò)誤"<<endl; return 1; break;else if(stri='+'|stri='-')int a=i+1;if(stra='/'|stra='*'|stra='%'|stra=')'|stra='.'|stra='')cout<<"表達(dá)式有錯(cuò)誤"<<endl;return 1;break;else if(isdigit(s

12、tri)!=0)int a=i+1;if(stra='(')cout<<"表達(dá)式有錯(cuò)誤"<<endl;return 1;break;else if(isdigit(stri)=0&&stri!='+'&&stri!='-'&&stri!='*'&&stri!='/'&&stri!=''&&stri!='%'&&stri!='

13、;('&&stri!=')'&&stri!='.')cout<<"表達(dá)式有錯(cuò)誤"<<endl;return 1;break;else if(stri='.')int a=i+1;if(isdigit(stra)=0)cout<<"表達(dá)式有錯(cuò)誤"<<endl; return 1; break;while(i=str.length()-1)cout<<"表達(dá)式正確"<<endl;r

14、eturn 2;break;elsecout<<"表達(dá)式有錯(cuò)誤"<<endl;return 1;double calculate(string exp)stack<double> number;double digit;string str=""for(int i=0;i<int(exp.length();i+)if(isdigit(expi)|expi='.')str=str+expi;else if(expi=' ') const char*p=str.c_str();digi

15、t=atof(p);/string轉(zhuǎn)換為doublenumber.push(digit);str=""else/(expi!='.'&&expi!=' '&&!isdigit(expi)&&number.size()>=2) double result;double right;double left;right=number.top();number.pop();left=number.top();number.pop();switch(expi)case '+':res

16、ult=left+right;number.push(result);break;case '-':result=left-right;number.push(result);break;case '*':result=left*right;number.push(result);break;case '/':result=left/right;number.push(result);break;case '%':int(result)=int(left)%int(right);number.push(result);break;

17、case '':result=pow(left,right);number.push(result);break;double finalresult=number.top();number.pop();return finalresult;void main()int x=1;cout<<"計(jì)算表達(dá)式"<<endl;cout<<"支持加+ 減- 乘* 除/ 整數(shù)取余% 次冪 小括號(hào)()"<<endl;while(x=1)string str;cout<<"請(qǐng)輸入表達(dá)式

18、，最后不加等號(hào)"<<endl; cin>>str;string exp;int a=examine(str);if(a=2)exp=transform(str); cout<<str<<"="<<calculate(exp)<<endl;cout<<"繼續(xù)運(yùn)算請(qǐng)輸入Y，否則按任意鍵退出"<<endl;char ch;cin>>ch;if(ch='Y'|ch='y')x=1;elsex=2;system("pause");六、運(yùn)行結(jié)果：這個(gè)是一開始運(yùn)行的情況。輸入完表達(dá)式后會(huì)判斷表達(dá)式是否正確，如果