数据结构
课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
班级:11021001
姓名:桂豪纵
学号:2010302672
2012年7月12日
一、需求分析
设计一个程序,演示用算符优先法对算术
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式求值的过程。利用算符优先关系,实现对算术四则混合运算表达式的求值。
(1)输入的形式:表达式,例如2*(3+4)=或者2*(3+4)#;
包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')';
(2)输出的形式:运算结果,例如77,56.24;
(3)程序所能达到的功能:对表达式求值并输出结果。
二、概要设计:
本课程设计需要用到抽象数据类型栈存储表达式。本部分给出栈的类型定义与表达式求值操作描述。
1、存储结构(顺序栈):
template
class Sqstack
{
private:
SElemType *base;
SElemType *top;
int stacksize;
protected:
public:
Sqstack();
Status InitStack();
Status Push(SElemType e);
Status Pop(SElemType *e);
Status StackEmpty();
Status DestroyStack();
Status GetTop(SElemType *e);
};
2、基本操作:
Status InitStack()
操作结果:初始化一个空栈s。
Status GetTop(SElemType *e)
操作结果:得到s的栈顶元素并用e带回。
Status Push(SElemType e)
操作结果:向栈s中压入元素e。
Status Pop(SElemType *e)
操作结果:弹出栈s栈顶元素,并用e带回。
Status StackEmpty();
操作结果:判断栈是否为空,若空这返回TRUE,否则返回FLASE。
Status DestroyStack();
操作结果:销毁整个栈。
三、详细设计
本部分主要给出表达式求值的实现算法
1、初始化一个空栈
template
Status Sqstack ::InitStack()
{
base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!base) exit(OVERFLOW);
top = base;
stacksize = STACK_INIT_SIZE;
return OK;
}
2、读取栈顶元素
template
Status Sqstack ::GetTop(SElemType *e)
{
if(top>base)
{
*e=*(top-1);
return OK;
}
else
return FALSE;
}
3、向栈中压入元素e
template
Status Sqstack ::Push(SElemType e)
{
if(top-base>=stacksize)
{
base = (SElemType*)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!base)exit(OVERFLOW);
top = base+stacksize;
stacksize+=STACKINCREMENT;
}
*(top)++=e;
return OK;
}
4、弹出栈顶元素
template
Status Sqstack ::Pop(SElemType *e)
{
if(base == top)
return ERROR;
*e=*(--top);
return OK;
}
5、判断栈是否为空
template
Status Sqstack ::StackEmpty()
{
if(top==base)
return ERROR;
else
return FALSE;
}
6、销毁栈
template
Status Sqstack ::DestroyStack()
{
free(base);
base = NULL;
stacksize = 0;
top = NULL;
return OK;
}
7、比较两运算符优先级
int compare(char p1,char p2)
{
switch(p1)
{
case '-':
case '+':
switch(p2)
{
case ')':
case '+':
case '-':
case '*':
case '/':
return -1;
case '(':
case '#':
return 1;
}
break;
case '/':
case '*':
switch(p2)
{
case '+':
case '-':
case '(':
case '#':
return 1;
case '*':
case '/':
case ')':
return -1;
}
break;
case '(':
switch(p2)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case '#':
return 1;
case ')':
return ERROR;
}
break;
case ')':
switch(p2)
{
case '+':
case '-':
case '*':
case '/':
return -1;
case '(':
return 0;
case ')':
return ERROR;
case '#':
return ERROR;
}
break;
case '=':
switch(p2)
{
case '+':
case '-':
case '*':
case '/':
case ')':
return -1;
case '(':
return ERROR;
}
break;
}
return 0;
}
8、四则运算
template
T chengfa(T x1,T x2)
{
return x1*x2;
}
template
T chufa(T x1,T x2)
{
return x1/x2;
}
template
T jiafa(T x1,T x2)
{
return x1+x2;
}
template
T jianfa(T x1,T x2)
{
return x1-x2;
}
9、主函数进行表达式求值
#include "stdafx.h"
#include
#include "Stack.cpp"
using namespace std;
typedef float Type;
int compare(char p1,char p2);
template
T chengfa(T x1,T x2);
template
T chufa(T x1,T x2);
template
T jiafa(T x1,T x2);
template
T jianfa(T x1,T x2);
int _tmain(int argc, _TCHAR* argv[])
{
Sqstack sqstack1;
sqstack1.InitStack();
Sqstack sqstack2;
sqstack2.InitStack();
sqstack2.Push('#');
char ch,tm,tempch;
char e='#';
Type temp1,temp2;
double j=1.0;
bool point=false;
Type t1;
cin>>ch;
tempch = '#';
while(ch!='='||e!='#')
{
if((ch>='0'&&ch<='9')||ch=='.')
{
if(ch=='.')
{
tempch='#';
point=true;
}
else
{
if((tempch>='0'&&tempch<='9')||tempch=='.')
{
if(point)
{
j=j/10;
sqstack1.Pop(&t1);
sqstack1.Push(t1+(ch-48)*j);
}
else
{
sqstack1.Pop(&t1);
sqstack1.Push(t1*10+Type(ch-48));
}
}
else
sqstack1.Push(Type(ch-48));
}
}
else
{
point=false;
j=1.0;
while(compare(ch,e)<0)
{
sqstack2.Pop(&tm);
sqstack1.Pop(&temp1);
sqstack1.Pop(&temp2);
switch(tm)
{
case '+':
sqstack1.Push(jiafa(temp1,temp2));
break;
case '-':
sqstack1.Push(jianfa(temp2,temp1));
break;
case '*':
sqstack1.Push(chengfa(temp2,temp1));
break;
case '/':
sqstack1.Push(chufa(temp2,temp1));
break;
}
sqstack2.GetTop(&e);
}
if(compare(ch,e)>0)
{
sqstack2.Push(ch);
}
else if(compare(ch,e)==0)
{
sqstack2.Pop(&tm);
}
sqstack2.GetTop(&e);
}
if(ch!='=')
{
tempch = ch;
cin>>ch;
}
}
sqstack1.GetTop(&temp1);
cout<
本文档为【表达式求值实验报告 (桂豪纵)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。