栈的应用之表达式求值.doc

学 生 实 验 报 告学 院： 软件与通信工程学院 课程名称： 数据结构 专业班级： 电信141班 姓 名： 学 号： 014 学生实验报告（1）学生姓名学号同组人：无实验项目栈的应用之表达式求值必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点H113实验仪器台号 指导教师黄淑英实验日期及节次一、实验综述1、实验目的及要求掌握栈在表达式求值算法中的应用。2、实验仪器、设备或软件电脑二、实验过程（实验步骤、记录、数据、分析）打开电脑，打开Microsoft visual C+6.0、新建、Win32 Conosle Application建一个空工程文件、选择源文件、开始编写程序 #include#include#include#include #include #include #include #include #include const char oper7 = +, -, *, /, (, ), = ;/建立一个一维数组放置运算符#define MAXSIZE 100#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef char SElemType; typedef struct StackNode/创建一个单链表Status data;struct StackNode *next; StackNode, *LinkStack;Status InitStack(LinkStack &S)/初始化 S=NULL;return OK;Status StackEmpty(LinkStack S) if (!S)return true;return false;Status Push(LinkStack &S,SElemType e)/入栈StackNode *p;p=new StackNode;if (!p) return OVERFLOW;p-data=e;p-next=S;S=p;return OK;Status Pop(LinkStack &S,SElemType &e)/出栈StackNode *p;if (S=NULL)return ERROR;e=S-data;p=S;S=S-next;delete p;return OK;SElemType GetTop(LinkStack S) /取栈顶元素if (S!=NULL)return S-data;Status In(char ch) /判断ch是否为运算符for (int i = 0; i 7; i+) if (ch = operi) return true;return false;/判断运算符优先级char Precede(char theta1, char theta2) if (theta1 = ( & theta2 = ) | (theta1 = = & theta2 = =) return =;else if (theta1 = ( | theta1 = = | theta2 = ( | (theta1= + | theta1 = -) & (theta2 = * | theta2 = /) return ;char Operate(char first, char theta, char second) /计算两数运算结果switch (theta) case +:return (first-0)+(second-0)+48;case -:return (first-0)-(second-0)+48;case *:return (first-0)*(second-0)+48;case /:return (first-0)/(second-0)+48;return 0;/算术表达式求值的算符优先算法/设OPTR和OPND分别为运算符栈和操作数栈char EvaluateExpression()char ch;SElemType a,b,theta,x;LinkStack OPND,OPTR;InitStack(OPND);InitStack(OPTR);Push(OPTR,=);cinch;while(ch!=|GetTop(OPTR)!=)if(!In(ch)Push(OPND,ch);cinch;elseswitch(Precede(GetTop(OPTR),ch)case ch;break;case :Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;case =:Pop(OPTR,x);cinch;break;return GetTop(OPND);/*int menu() int c;cout0-9以内的多项式计算endl;cout1.计算endl;cout0.退出n endl;coutc;return c;*/void main() while (1) switch (1/*menu()*/) case 1: cout 请输入要计算的表达式（操作数和结果都在0-9的范围内，以=结束）： endl;int res=EvaluateExpression();cout计算结果为res-48endlendl;break;case 0:c