壹、需求分析
1、 功能:疏如壹行表達式,若表達式有誤,則輸出“表達式有錯” ,否則計算出表達式的值並輸出。 運算符包括加、減、乘、除、乘方、壹目減。 括號均為小括號,但可以層層嵌套。操作數可以是浮點數,也包括有多個字母組成的變量。
2、 輸入的形式為表達式,按回車結束。輸入值的範圍不超過浮點數的範圍。含有變量,變量名由字母組成,大小寫不限。
3、 若計算結果為整數,則輸出整數,若含有小數,則輸出浮點數。
二、概要設計
1、 總體思路,先讀入壹行表達式,用壹個字符數組存儲。然後依次讀每個字符,進行判斷。邊讀入邊進行計算。程序中用到了兩個棧,壹個字符棧以及壹個數字棧,分別用來存儲運算符和數字,根據運算符的優先順序進行計算。最後輸出結果。
2、程序包括幾個模塊,主函數和幾個基本函數。
說明幾個函數:
bool stackempty(save1 s)用來判斷操作數棧s是否為空。
void push(save1 &s,char e)若棧滿則輸出“棧已滿”,否則將元素e入棧
void pop(save1 &s, char &e)若棧為空則輸出“棧為空”,否則將棧頂元素賦給e
bool stackempty2(save2 s)用來判斷運算符棧s是否為空。
void push2(save2 &s, char e)若運算符棧滿則輸出“棧已滿”,否則將元素e入棧
void pop2(save2 &s, char &e)若棧為空則輸出“棧為空”,否則將棧頂元素賦給e
int in(char e)返回運算符e在棧內的優先級別
int out(char e) 返回運算符e在棧外的優先級別
void count(char a,char ope, char b)將a、b進行相應的運算,並將運算結果入棧
3、具體操作步驟:
1、先讀入壹行表達式,用壹個字符數組line[]存儲
2、依次讀入每個字符並進行處理同是進行表達式判錯:
1. 遇數字,則繼續判斷下壹個字符,直到下壹個字符不是數字且不是小數點,若該數含有兩個小以上數點,則表示輸入錯誤。否則即可保證該操作數是完整的浮點數,然後將該數入操作數棧。
若數字不是表達式的最後壹位,且數字後面跟的不是“+、-、*、/、^、)”,則為表達式錯誤
2. 遇運算符,則分兩種情況:
1、若運算符為負號(該運算符為符號的情況有兩種:壹為負號在最開頭,壹為符號前面是“(” ),則先將0入操作數棧,然後再將負號入運算符棧。
2、該運算符不是負號則與運算符棧的棧頂元素比:
(1) 若棧頂元素優先級低, 新輸入的運算符入棧。
(2) 若棧頂元素優先級高,
1) 從符號棧彈出壹個運算符,
2) 從對象棧彈出壹個/兩個操作數,
3) 運算結果壓入對象棧。
(3) 優先級相等,則棧頂元素出棧,與輸入元素對消。
若“(、+、-、*、/、^”放在表達式最後面,則表達式錯誤
若“+、-、*、/、^”後面跟的不是數字或者變量,表達式錯誤
3、遇字母變量,則繼續判斷下壹個字符,直到下壹個字符不是字母變量,即可保證該變量是完整的,然後輸出“請輸入變量的值”,再將輸入的變量值入操作數棧。
若變量後面跟的不是“+、-、*、/、^、)”,則表達式錯誤
4、若所讀的該字符不是上述情況中的壹種,則表達式錯誤
3、當將所有的字符都讀壹遍之後,若表達式正確的話,則必然不含有“(”或者“)”。即若運算符棧中含有“(”或者“)”,則表達式必錯誤。 再考慮表達式正確的情況:運算符棧可能為空,則操作符棧中必剩下壹個操作數,即最後的結果。若不為空,則留在運算符棧中的運算符的優先級別從棧頂至棧底依次遞減。故可從運算符棧頂開始彈出壹個運算符,從操作數棧中彈出兩個操作數進行運算,再將運算結果入操作數棧,壹直循環至運算符棧為空。此時操作數棧剩下的唯壹壹個操作數就是運算結果。
三、結論及體會
1、實驗結論
a)、實驗完成了題目的要求,自己添加了對浮點數的操作,並進行判錯。
b)、編寫代碼基本上能夠滿足編程規範的要求,代碼的變量命名,以及註釋的書寫,基本能按照要求進行。
b)、將數據結構中的隊列和堆棧的知識復習到,並且學會創新,在代碼的編寫中,學習了編程規範,學習了結構化編程。
2、實驗體會
a)、通過本設計實驗將數據結構中的堆棧和隊列的知識復習到,並且能夠自己設計壹些東西,學會了在設計實驗過程時的基本步驟。基本上能夠有條理的解決這些問題。
b)、在試驗中遇到了很多的問題,都是以前沒有發現的,這些問題設計的方面很多,有以前的C++基礎的,也有最近學習的數據結構的知識。通過實驗的設計,讓我發現了自己的不足。自己在學習知識上面的漏洞。自己在細節方面的考慮還不夠全面,很多細節都是通過調試才發現的。比如剛開始時忘了考慮變量之前有負號的情況以及將整個式子讀壹遍之後,棧中的操作數可能還有剩,還得繼續進行計算等。希望通過彌補這些發現的漏洞,提高自己的專業知識水平。
c)、設計過程中的解決問題的方法,讓我明白了如何學習會更有效。如何學習才不會耽誤太多的時間。也學會了解決問題的壹般方法:向老師、同學請教,借助網絡等等。
d)、實驗過程中也走了很多的彎路,由於在開始設計的時候思路不時很清晰,對於壹些問題不能很好的提出解決問題的方法,在設計過程中,代碼總是重復的修改,在很多問題上,代碼並不時最優的。相信在以後的學習中,隨著知識的增多,問題會逐漸得到解決。
四、程序源代碼
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
#define MAX 1000
struct save1
{
float n[MAX];
int top;
}stack1;
struct save2
{
char n[MAX];
int top;
}stack2;
//stack1存儲數字,stack2存儲運算符號.
bool stackempty(save1 s)//判斷是否為空
{
if (s.top== -1)
return 1;
else
return 0;
}
bool stackempty2(save2 s)//判斷是否為空
{
if (s.top== -1)
return 1;
else
return 0;
}
void push(save1 &s,float e)//將e入棧
{
if(s.top==MAX-1)
{
cout<<"棧已滿"<<endl;
return ;
}
s.top++;
s.n[s.top]=e;
}
void push2(save2 &s,char e)//將e入棧
{
if(s.top==MAX-1)
{
cout<<"棧已滿"<<endl;
return ;
}
s.top++;
s.n[s.top]=e;
}
void pop(save1 &s,float &e)//將棧頂元素出棧,存到e中
{
if(s.top==-1)
{ cout<<"棧為空"<<endl; }
else
{e=s.n[s.top]; s.top--; }
}
void pop2(save2 &s,char &e)//將棧頂元素出棧,存到e中
{
if(s.top==-1)
{ cout<<"棧為空"<<endl; }
else
{e=s.n[s.top]; s.top--; }
}
int in(char e)//e在棧內的優先級別
{
if(e=='-' || e=='+') return 2;
if(e=='*' || e=='/') return 4;
if(e=='^') return 5;
if(e=='(') return 0;
if(e==')') return 7;
return -1;
}
int out(char e)//e在棧外的優先級別
{
if(e=='-' || e=='+') return 1;
if(e=='*' || e=='/') return 3;
if(e=='^') return 6;
if(e=='(') return 7;
if(e==')') return 0;
return -1;
}
void count(float a,char ope,float b)//進行計算並將計算結果入棧
{
float sum;
if(ope=='+') sum=a+b;
if(ope=='-') sum=a-b;
if(ope=='*') sum=a*b;
if(ope=='/') sum=a/b;
if(ope=='^') sum=pow(a,b);
push(stack1,sum);
}
int main()
{
int i=0,len,j,nofpoint,g=0;//len表示輸入式子的長度。 g表示讀入的字符是否是字母變量、數字以及運算符。
float a,b;//a、b用來存儲操作數棧中彈出的操作數,便於代入函數中進行計算。
char line[MAX],operate,temp[20];
cout<<"請輸入表達式"<<endl;
cin>>line;
len=strlen(line);
stack1.top=-1;//將棧置為空
stack2.top=-1;//將棧置為空
while(1)
{
g=0;
if(isdigit(line[i]))//若讀入的字符為數字,則繼續判斷下壹個字符,直到下壹個字符不是數字或者不是小數點,即可保證該操作數是完整的小數,然後將該數入操作數棧。
{
j=0; g=1;
nofpoint=0;//記錄所存的數中小數點的個數
while(isdigit(line[i]) || line[i]=='.')
{
if(line[i]=='.') nofpoint++;
temp[j++]=line[i];
i++;
if(i>=len) break;
}
if( nofpoint>1 || (i<len&&(line[i]!='-' && line[i]!='+' && line[i]!='*' && line[i]!='/' && line[i]!='^' && line[i]!=')')) )
{ cout<<"表達式有錯"<<endl; return 0; }//所存數中含有不止壹個小數點,或者數字後面跟的不是“+、-、*、/、^、)”,則為錯誤
temp[j]='\0';
b=atof(temp);
push(stack1,b);
if(i>=len) break;
}
else
{
if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' ||
line[i]=='^' || line[i]=='(' || line[i]==')' ) //若讀入的字符為運算符的情況
{
g=1;
if(line[i]=='(' && i==len) { cout<<"表達式有錯"<<endl; return 0; }// “(”放表達式最後面,錯誤
if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' || line[i]=='^')
{
if(i==len) { cout<<"表達式有錯"<<endl; return 0; }//“+、-、*、/、^”放在表達式最後面,錯誤
if( (!isdigit(line[i+1])) && (!isalpha(line[i+1])) && line[i+1]!='(')//“+、-、*、/、^”後面跟的不是數字或者變量,錯誤
{ cout<<"表達式有錯"<<endl; return 0; }
}
if(line[i]=='-' && (i==0 || line[i-1]=='(' ))//運算符是負號
{
push(stack1,0);
push2(stack2,line[i]);
i++;
}
else
{ //讀入的運算符與運算符棧的棧頂元素相比,並進行相應的操作
if(in(stack2.n[stack2.top])<out(line[i])||stackempty2(stack2)) { push2(stack2,line[i]);i++;}
else
if(in(stack2.n[stack2.top])==out(line[i])) {i++; stack2.top--;}
else
if(in(stack2.n[stack2.top])>out(line[i]))
{
pop(stack1,a);
pop(stack1,b);
pop2(stack2,operate);
count(b,operate,a);
}
if(i>=len) break;
}
}
else
{
if(isalpha(line[i]))//讀入的字符是字母變量的情況
{
g=1;
cout<<"請輸入變量";
while( isalpha(line[i])) { cout<<line[i]; i++; }
cout<<"的值"<<endl;
cin>>b;
push(stack1,b);
if(i>=len) break;
if(line[i]!='-' && line[i]!='+' && line[i]!='*' && line[i]!='/' && line[i]!='^' && line[i]!=')')//變量後面跟的不是“+、-、*、/、^、)”,則為錯誤
{ cout<<"表達式有錯"<<endl; return 0; }
}
}
}
if(g==0) { cout<<"表達式有錯"<<endl; return 0; }//g=0表示該字符是不符合要求的字符
}
while(stack2.top!=-1)//讀入結束後,繼續進行操作,直到運算符棧為空
{
pop(stack1,a);
pop(stack1,b);
pop2(stack2,operate);
if(operate=='(' || operate==')') //括號多余的情況
{ cout<<"表達式有錯"<<endl; return 0; }
count(b,operate,a);
}
cout<<stack1.n[stack1.top]<<endl;
return 0;
}