《長(zhǎng)沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)棧的實(shí)現(xiàn)及應(yīng)用算術(shù)表達(dá)式求值實(shí)驗(yàn)報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《長(zhǎng)沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)棧的實(shí)現(xiàn)及應(yīng)用算術(shù)表達(dá)式求值實(shí)驗(yàn)報(bào)告.doc（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、批
閱
實(shí) 驗(yàn) 報(bào) 告
年級(jí) 班號(hào) 學(xué)號(hào) 姓名
實(shí)驗(yàn)名稱： 棧的實(shí)現(xiàn)及其應(yīng)用：算術(shù)表達(dá)式的計(jì)算
實(shí)驗(yàn)日期 2016年12月 2日
實(shí)驗(yàn)報(bào)告撰寫內(nèi)容
一、實(shí)驗(yàn)環(huán)境
二、實(shí)驗(yàn)?zāi)康?
三、實(shí)驗(yàn)內(nèi)容
四、數(shù)據(jù)結(jié)構(gòu)與算法思想描述
五、程序清單
六、程序執(zhí)行結(jié)果及其分析
計(jì)算機(jī)科學(xué)與技術(shù)系
2016年制
一、 實(shí)驗(yàn)環(huán)境
32位操作系統(tǒng)下的Window平臺(tái) Microsoft Visual C++
二、 實(shí)驗(yàn)?zāi)康?
掌握棧的實(shí)現(xiàn)及使用
三、 實(shí)驗(yàn)內(nèi)容
1.
2、實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)
2.實(shí)現(xiàn)棧的基本操作的有關(guān)算法
3.利用棧解決*算術(shù)表達(dá)式求值問(wèn)題
四、 數(shù)據(jù)結(jié)構(gòu)與算法思想描述
順序讀取中綴表達(dá)式：
1、 當(dāng)遇到數(shù)字時(shí)，將數(shù)字入數(shù)字棧
2、 當(dāng)遇到操作符時(shí)，與操作符棧棧頂比較：
If(當(dāng)前操作符優(yōu)先級(jí)大于操作符棧棧頂?shù)膬?yōu)先級(jí))
If(非”)”操作符)
將當(dāng)前操作符進(jìn)操作符棧;
Else
While(操作符棧棧頂不等于”(“)
取操作符棧棧頂及數(shù)字棧的兩個(gè)數(shù)進(jìn)行運(yùn)算，并將結(jié)果壓入數(shù)字棧;
Else
If(非(“操作符)
While(操作符棧棧頂不等于”(“)
取操作符棧棧頂及數(shù)字棧的兩個(gè)數(shù)進(jìn)行運(yùn)算，并將結(jié)果壓入數(shù)字
3、棧;
Continue;(直到當(dāng)前操作符比棧頂操作符優(yōu)先級(jí)大)
Else
將當(dāng)前操作符進(jìn)操作符棧;
3、 While(操作符棧非空)
操作符棧棧頂及數(shù)字棧的兩個(gè)數(shù)進(jìn)行運(yùn)算，并將結(jié)果壓入數(shù)字棧;
4、 在數(shù)字棧取最后結(jié)果并輸出。
五、 程序清單
//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666
//100+(-100)-(-10^2) = 100
//(((2016-2017+(((2015-2014)))))) = 0
//-1+(((((
4、((((1^0))))))))+100%10^2 = 0
#include
#include
#include
#include
#include
#include
5、tack;
//初始化棧
void InitStack(Stack *S)
{
S->charTop = S->TypeTop = 0;
}
//判斷charStack是否為空
bool IsEmpty_Char(Stack S)
{
return S.charTop == 0;
}
//判斷TypeStack是否為空
bool IsEmpty_Type(Stack S)
{
return S.TypeTop == 0;
}
//判斷charStack是否為滿
bool IsFull_Char(Stack S)
{
return S
6、.charTop == MAX;
}
//判斷TypeStack是否為滿
bool IsFull_Type(Stack S)
{
return S.TypeTop == MAX;
}
void Push_Char(Stack *S, char ch)
{
//charStack不為滿則入棧，否則輸出提示
if(!IsFull_Char(*S))
S->charStack[S->charTop++] = ch;
else
cout << " The CharStack Is Full! " << endl;
}
void Push_Typ
7、e(Stack *S, Type a)
{
//TypeStack不為滿則入棧，否則輸出提示
if(!IsFull_Type(*S))
S->TypeStack[S->TypeTop++] = a;
else
cout << " The TypeStack Is Full! " << endl;
}
char Pop_Char(Stack *S)
{
if(!IsEmpty_Char(*S))
{
S->charTop--;
return S->charStack[S->charTop];
}
else
cout << "
8、The CharStack Is Empty! " << endl;
return -1;
}
Type Pop_Type(Stack *S)
{
if(!IsEmpty_Type(*S))
{
S->TypeTop--;
return S->TypeStack[S->TypeTop];
}
else
cout << " The TypeStack Is Empty! " << endl;
return -1;
}
char Top_Char(Stack S)
{
if(!IsEmpty_Char(S))
return S
9、.charStack[--S.charTop];
else
cout << " The CharStack Is Empty! " << endl;
return -1;
}
Type Top_Type(Stack S)
{
if(!IsEmpty_Type(S))
return S.TypeStack[--S.TypeTop];
else
cout << " The TypeStack Is Empty! " << endl;
return -1;
}
Type Calculate(Type left, Type right, char
10、 op)
{
Type value = 0;
switch(op)
{
case +: value = left + right; break;
case -: value = left - right; break;
case *: value = left * right; break;
case /: if(right != 0)
value = left / right;
else
cout << "被除數(shù)不能為零!" << endl;
break;
case %: if(right != 0)
11、value = (int)left % (int)right;
else
cout << "被余數(shù)不能為零!" << endl;
break;
case ^: value = pow(left,right);
/*value = 1;
if(right >= 0)
while(right--)
value *= left;
else
{
right = -right;
while(right--)
value /= left;
}*/
}
re
12、turn value;
}
void Computer(char *mid_equotion, Type len)
{
Type right, left , result;
char *p_mid_equotion = mid_equotion;
char after_equotion = ;
map Oper;
Oper[#] = 1; Oper[(] = 2; Oper[+] = 3;
Oper[-] = 3; Oper[*] = 4; Oper[/] = 4;
Oper[%] = 4; Oper[^] = 5; Ope
13、r[)] = 6;
Stack MyStack;
InitStack(&MyStack);
Push_Char(&MyStack,#);
char top_oper, current_oper;
for(;*p_mid_equotion != \0;)
{
top_oper = Top_Char(MyStack);
current_oper = *p_mid_equotion;
if(!Oper[current_oper])
{
Push_Type(&MyStack,strtod(p_mid_equotion, &p_mi
14、d_equotion));
continue;
}//end if
else //為操作符
{
if(Oper[current_oper] > Oper[top_oper])
{
if(current_oper != ))
Push_Char(&MyStack,current_oper);
else
{
while(top_oper != ()
{
right = Pop_Type(&MyStack);
if(!IsEmpty_Type(MyStack))
15、 left = Pop_Type(&MyStack);
else
left = 0;
Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack)));
Pop_Char(&MyStack);
top_oper = Top_Char(MyStack);
}
Pop_Char(&MyStack);
}//end else
}//end if
else
{
if(current_oper =
16、= ()
{
Push_Char(&MyStack,current_oper);
if(*(p_mid_equotion + 1) == -)
Push_Type(&MyStack,0);
}
else
{
right = Pop_Type(&MyStack);
if(!IsEmpty_Type(MyStack))
left = Pop_Type(&MyStack);
else
left = 0;
Push_Type(&MyStack,Cal
17、culate(left, right, top_oper));
Pop_Char(&MyStack);
continue;
}
}//end else
}//end else
p_mid_equotion++;
}//end for
top_oper = Pop_Char(&MyStack);
while(top_oper != #)
{
right = Pop_Type(&MyStack);
if(!IsEmpty_Type(MyStack))
left = Pop_Type(&MyStack);
18、
else
left = 0;
Push_Type(&MyStack,Calculate(left, right, top_oper));
top_oper = Pop_Char(&MyStack);
}
// cout << setprecision(6) << "\nThe Result = " << (result = Pop_Type(&MyStack)) << endl;
printf("The Result = %lf\n\n",(result = Pop_Type(&MyStack)));
}
int main()
{
char s[MAX] = "";
Type i = 0;
cout << "請(qǐng)輸入你要求值的表達(dá)式!(以-1結(jié)束)\n";
while(cin >> s && strcmp(s,"-1") != 0)
{
Computer(s,strlen(s));
cout << "請(qǐng)輸入你要求值的表達(dá)式!(以-1結(jié)束)\n";
}
return 0;
}
六、 程序執(zhí)行結(jié)果及其分析
對(duì) “+” , “-” , “*” , “/” , “%” , “^” 運(yùn)算的實(shí)現(xiàn)
可運(yùn)算多位數(shù)和小數(shù)，求余，求平方，括號(hào)里包含負(fù)數(shù)如（-1），及首個(gè)數(shù)字為負(fù)數(shù)如-1+1
長(zhǎng)沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)棧的實(shí)現(xiàn)及應(yīng)用算術(shù)表達(dá)式求值實(shí)驗(yàn)報(bào)告.doc
