《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.doc》由会员分享，可在线阅读，更多相关《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.doc（13页珍藏版）》请在装配图网上搜索。
1、批
阅
实 验 报 告
年级 班号 学号 姓名
实验名称： 栈的实现及其应用：算术表达式的计算
实验日期 2016年12月 2日
实验报告撰写内容
一、实验环境
二、实验目的
三、实验内容
四、数据结构与算法思想描述
五、程序清单
六、程序执行结果及其分析
计算机科学与技术系
2016年制
一、 实验环境
32位操作系统下的Window平台 Microsoft Visual C++
二、 实验目的
掌握栈的实现及使用
三、 实验内容
1.
2、实现栈的存储结构
2.实现栈的基本操作的有关算法
3.利用栈解决*算术表达式求值问题
四、 数据结构与算法思想描述
顺序读取中缀表达式：
1、 当遇到数字时，将数字入数字栈
2、 当遇到操作符时，与操作符栈栈顶比较：
If(当前操作符优先级大于操作符栈栈顶的优先级)
If(非”)”操作符)
将当前操作符进操作符栈;
Else
While(操作符栈栈顶不等于”(“)
取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
Else
If(非(“操作符)
While(操作符栈栈顶不等于”(“)
取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字
3、栈;
Continue;(直到当前操作符比栈顶操作符优先级大)
Else
将当前操作符进操作符栈;
3、 While(操作符栈非空)
操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
4、 在数字栈取最后结果并输出。
五、 程序清单
//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 << "被除数不能为零!" << endl;
break;
case %: if(right != 0)
11、value = (int)left % (int)right;
else
cout << "被余数不能为零!" << 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 << "请输入你要求值的表达式!(以-1结束)\n";
while(cin >> s && strcmp(s,"-1") != 0)
{
Computer(s,strlen(s));
cout << "请输入你要求值的表达式!(以-1结束)\n";
}
return 0;
}
六、 程序执行结果及其分析
对 “+” , “-” , “*” , “/” , “%” , “^” 运算的实现
可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1
长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.doc
