长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告

1、批阅实 验 报 告 年级 班号 学号 姓名 实验名称： 栈的实现及其应用：算术表达式的计算 实验日期 2016年12月 2日实验报告撰写内容一、实验环境二、实验目的三、实验内容四、数据结构与算法思想描述五、程序清单六、程序执行结果及其分析计算机科学与技术系2016年制一、 实验环境32位操作系统下的Window平台 Microsoft Visual C+二、 实验目的掌握栈的实现及使用三、 实验内容1.实现栈的存储结构2.实现栈的基本操作的有关算法3.利用栈解决*算术表达式求值问题四、 数据结构与算法思想描述顺序读取中缀表达式：1、 当遇到数字时，将数字入数字栈2、 当遇到操作符时，与操作符栈

2、栈顶比较：If(当前操作符优先级大于操作符栈栈顶的优先级)If(非”)”操作符)将当前操作符进操作符栈;ElseWhile(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;ElseIf(非(“操作符)While(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;Continue;(直到当前操作符比栈顶操作符优先级大)Else将当前操作符进操作符栈;3、 While(操作符栈非空)操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;4、 在数字栈取最后结果并输出。五、 程序清单/10*82+16.3+5*(5.2*5

3、+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666/100+(-100)-(-102) = 100/(2016-2017+(2015-2014) = 0/-1+(10)+100%102 = 0#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<iomanip>#include<map>using namespace std;const int MAX = 105;typede

4、f double Type;typedef structType TypeStackMAX;char charStackMAX;int TypeTop, charTop;Stack;/初始化栈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

5、 IsFull_Char(Stack S)return S.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->charStackS->charTop+ = ch;elsecout << " The CharStack Is Full! " << endl;void Push_Typ

6、e(Stack *S, Type a)/TypeStack不为满则入栈，否则输出提示if(!IsFull_Type(*S)S->TypeStackS->TypeTop+ = a;elsecout << " The TypeStack Is Full! " << endl;char Pop_Char(Stack *S)if(!IsEmpty_Char(*S)S->charTop-;return S->charStackS->charTop;elsecout << " The CharStack Is

7、Empty! " << endl;return -1;Type Pop_Type(Stack *S)if(!IsEmpty_Type(*S)S->TypeTop-;return S->TypeStackS->TypeTop;elsecout << " The TypeStack Is Empty! " << endl;return -1;char Top_Char(Stack S)if(!IsEmpty_Char(S)return S.charStack-S.charTop;elsecout <<

8、" The CharStack Is Empty! " << endl;return -1;Type Top_Type(Stack S)if(!IsEmpty_Type(S)return S.TypeStack-S.TypeTop;elsecout << " The TypeStack Is Empty! " << endl;return -1;Type Calculate(Type left, Type right, char op)Type value = 0;switch(op)case '+':

9、value = left + right;break;case '-':value = left - right;break;case '*':value = left * right;break;case '/':if(right != 0)value = left / right;elsecout << "被除数不能为零!" << endl;break;case '%':if(right != 0)value = (int)left % (int)right;elsecout <

10、;< "被余数不能为零!" << endl;break;case '':value = pow(left,right);/*value = 1;if(right >= 0)while(right-)value *= left;elseright = -right;while(right-)value /= left;*/return value;void Computer(char *mid_equotion, Type len)Type right, left , result;char *p_mid_equotion = mid_

11、equotion;char after_equotion = ' 'map<char,Type> Oper;Oper'#' = 1;Oper'(' = 2;Oper'+' = 3;Oper'-' = 3;Oper'*' = 4;Oper'/' = 4;Oper'%' = 4;Oper'' = 5;Oper')' = 6;Stack MyStack;InitStack(&MyStack);Push_Char(&

12、MyStack,'#');char top_oper, current_oper;for(;*p_mid_equotion != '0')top_oper = Top_Char(MyStack);current_oper = *p_mid_equotion;if(!Opercurrent_oper)Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion);continue;/end ifelse/为操作符if(Opercurrent_oper > Opertop_oper)if(c

13、urrent_oper != ')')Push_Char(&MyStack,current_oper);elsewhile(top_oper != '(')right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack);Pop_Char(&MyStack);top_oper = Top_C

14、har(MyStack);Pop_Char(&MyStack);/end else/end ifelseif(current_oper = '(')Push_Char(&MyStack,current_oper);if(*(p_mid_equotion + 1) = '-')Push_Type(&MyStack,0);elseright = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type

15、(&MyStack,Calculate(left, right, top_oper);Pop_Char(&MyStack);continue;/end else/end elsep_mid_equotion+;/end fortop_oper = Pop_Char(&MyStack);while(top_oper != '#')right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack)left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&M

16、yStack,Calculate(left, right, top_oper);top_oper = Pop_Char(&MyStack);/cout << setprecision(6) << "nThe Result = " << (result = Pop_Type(&MyStack) << endl;printf("The Result = %lfnn",(result = Pop_Type(&MyStack);int main()char sMAX = ""Type i = 0;cout << "请输入你要求值的表达式!