表达式求值演示1

[目录]
1.需求分析
2.概要设计
3.详细设计
4.调试分析
5.用户手册


[原文]
一． 需求分析
1. 本次实验对堆栈进行一些实用化操作。运用所学的知识进行一些综合项目的实验。
2. 实验以用户和计算机的对话方式进行，即在计算机终端上显示“提示信息”，然后用户在键盘上输入程序规定的命令、相应的数据，然后显示运算结果。
3. 程序执行命令包括：输入表达式、是否继续运行（Y＝是/N＝否）。

二． 概要设计
堆栈的抽象数据类型定义为：
ADT Stacklist｛
数据对象：D＝{ai | ai∈Int，i＝1，2，…，n，n≥0}
数据关系：R1＝｛|ai-1，ai∈D，ai-1基本操作:
InitStack(&S)
操作结果：构造一个堆栈。
Push(&S，e)
初始条件：堆栈S已存在。
操作结果：将数据e压到堆栈S中。
Pop(&S，&e)
初始条件：堆栈S已存在。
操作结果：将堆栈S中顶元素弹出，并用e带回。
StackLength(S)
初始条件：堆栈S已存在。
操作结果：返回S中的元素个数。
GetTop(S,&e)
初始条件：堆栈S已存在。
操作结果：用e返回S的栈顶元素。
......














实验3：顺序栈基本操作

一 、实验目的

1．熟悉并能实现栈的定义和基本操作。

2．了解和掌握栈在递归和非递归算法的应用。

二 、实验要求

1．进行栈的基本操作时要注意栈“后进先出”的特性。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容

1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。

2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。

主要功能描述如下：

1、从键盘上输入表达式。

2、分析该表达式是否合法：

（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。

（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。

（3）若是其它字符，则返回错误信息。

3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

程序中应主要包含下面几个功能函数：

void initstack()：初始化堆栈

int Make_str()：语法检查并计算

int push_operate(int operate)：将操作码压入堆栈

int push_num(double num)：将操作数压入堆栈

int procede(int operate)：处理操作码

int change_opnd(int operate)：将字符型操作码转换成优先级

int push_opnd(int operate)：将操作码压入堆栈

int pop_opnd()：将操作码弹出堆栈

int cac

ulate(int cur_opnd)：简单计算+，-，*，/

double pop_num()：弹出操作数

3.已知函数t(n)=2*t(n/2)+n 其中t(0)=0，n为整数。编写程序实现：

(1)计算t(n)的递归算法。

(2)用链式栈实现计算t(n)的非递归算法。





四、思考与提高



1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？

2．栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？

3. 在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？