数据结构课程设计实验报告

发布 2022-10-05 20:16:28 阅读 3309

你一定要坚强,即使受过伤,流过泪,也能咬牙走下去。因为,人生,就是你一个人的人生。

题目:2.3 表达式求值问题。

1. 问题描述。

表达式是数据运算的基本形式。人们的书写习惯是中缀式,如:11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则,相同级别从左到右进行计算。表达式还有后缀式(如:22 7 4 — 3/11 +)和前缀式(如:

+ 11/*23—7 4 3)。后缀表达式和前缀表达式中没有括号,给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。

2. 数据结构设计。

本题中使用顺序栈用来存取运算符和运算数,顺序栈类的定义如下:

/顺序栈类定义。

template

class sqstack

private:

t *base;//栈底指针。

int top;//栈顶。

int stacksize;//栈容量。

public:

sqstack(int m);/构建函数。

~sqstack()/析构函数。

void push(t x);/入栈。

t pop();出栈。

t gettop();获取栈顶元素。

int stackempty();测栈空。

void clearstack();清空栈。

void stacktop();返回栈顶指针。

void stacktranverse();显示栈中元素。

3. 算法设计。

本题中规定的功能涉及的算法有:中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。

1) 中缀表达式求值。

首先定义了两个栈,分别用于存取运算符和运算数,如下:

sqstack op(20);

sqstackod(20);

然后依次读取表达式的一个字符c,如果c是运算数,入运算数栈。

如果c是运算符,把它与栈顶元素的优先级比较:

若“<”该运算符进栈,读入下一个字符,若“=”运算符退栈,消去一个括号读入下一个字符;

若“>”从运算符栈退出一个运算符,从运算数栈里退出两个运算数进行运算,并将结果入运算数栈。

这时需用到比较运算符优先级的函数:char precede(char t1,char t2)

/算符的优先级比较。

重复上述过程直到把表达式扫描完,操作数栈的栈顶元素为计算结果。算法如下:

case'<'栈顶元素优先权低。

c=*exp++;

break;

case'='x= /脱括号并接收下一字符。

c=*exp++;

break;

case'>'theta= 退栈并将运算结果入栈。

if(theta=='theta=='

cout<<"表达式有误!";

exit(0);

b=if(b==0)

cout<<"表达式有误!"

if(cout<<"表达式有误!"

2)将中缀表达式转换为后缀表达式。

从左向右读取表达式,读到运算数把它输出;

读到运算符f2,把运算符栈顶元素的算符优先级f1进行比较:

若“f1若“f1=f2”:从运算符栈退出一个运算符,不输出;

若“f1>f2”,从运算符栈退出一个运算符,从运算数栈里输出所有比f2优先级高的运算符,直至栈顶算符优先级小于f2,f2入运算符栈。

具体算法如下:

case'<'栈顶元素优先权低。

c=*exp++;break;

case'='x= /脱括号并接收下一字符。

c=*exp++;break;

case'>'postexp[i++]运算符出栈输出。

3)将中缀表达式转换为前缀表达式。

将中缀式入栈再依次从栈中读取元素:

如果是操作数把它加入一个数组中;

如果是运算符:

若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素,则此运算符入栈;否则,栈顶运算符出栈并加入数组中;

若是左括号,栈中元素逐个出栈加入数组中,直到遇到右括号。

最后数组中的元素序列为中缀式的逆序,将数组中的元素入栈再出栈就得到前缀式。

部分算法如下:

sqstackst(20);

sqstacksp(20);

sqstackop(20);

while(*exp利用栈得到中缀式的逆序。

while(!

if(x=='

while((x=='x=='x=='x=='

if(x=='

while(!

s[j]='0';

while(s[i]!=0')

while(!

preexp[k++]再次求逆序得到前缀式。

4)后缀表达式求值。

创建一个栈,作为运算数栈。

读取表达式:

若是运算数,入运算数栈;

若是运算符,从运算数栈退出两个运算数,进行运算,并把运算结果入运算数栈。

最后,栈顶元素即为表达式的值。

具体算法如下:

sqstack od(20);

c=*postexp++;

while(c!='0')

if(in(c))/c为运算符。

c=*postexp++;

v= (5)前缀表达式求值。

创建栈st和栈od用于存取表达式逆序和运算数,利用栈得到前缀表达式的逆序存入栈st;

栈st出栈,为x:

若x是运算数,则把x存入数组,直至x不是运算数;

若x是运算符,则从运算数栈退出两个运算数,进行运算,并把运算结果入运算数栈。

最后,栈顶元素即为表达式的值。

数据结构课程设计实验报告

数据结构。课程设计报告。xx大学计算机xxxx学院。计算机系 08级软件工程专业xx班。xxx学号 0823xxxxxx 班内序号 xx 2010年11月15日。任务 参加运动会有n个学校,学校编号为1 n。比赛分成m个男子项目,和w个女子项目。项目编号为男子1 m,女子m 1 m w。不同的项目取...

数据结构课程设计实验报告

仲恺农业工程学院。课程设计报告。2010 2011年度第1学期 名称 数据结构 课程设计 题目 学生成绩管理系统 院系 计算科学学院 班级 信息与计算科学信计091,092 学号 200911314116 200911314214 学生姓名 许建城刘汉明 指导教师 吴东庆。设计周数1作者1 许建城贡...

数据结构课程设计实验报告

江苏大学计算机学院。软件工程课程设计报告书。课程名称数据结构课程设计总评成绩。学生姓名 学号卢江涛3100608047 学生专业班级软件工程软件1002班。指导教师姓名王新胜。一 问题描述。以邻接表的方式确定有向网,完成 1.建立并显示它的邻接链表 2.以非递归的方式进行深度优先遍历,显示遍历的结果...