数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序.docx
《数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序.docx》由会员分享，可在线阅读，更多相关《数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序
数据结构实习报告：
设计一个演示用运算优先法对算数表达式求值过程的程序
实习报告题目：
设计一个演示用运算优先法对算数表达式求值过程的程序。
班级：
姓名：
学号：
完成日期：
一、需求分析
1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.
2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。
3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。
4测试数据见原题。
5程序执行的命令包括：
（1）
建立算数表达式；
（2）
得到运算表达式的值；
（3）
演示运算过程。
二、概要设计
1.
设定栈的抽象数据类型定义：
ADT
Stack{
数据对象
D＝{
ai
|
ai
∈charSet,i=1,2,.,n,n≥0
}
数据关系：
R1＝{
|
ai-1,ai∈D,i=2,.,n
}
（约定an
端为栈顶，a1
端为栈底）
基本操作：
InitStack（
inttop;
int
stacksize;
}SqStack1;//操作数栈
typedef
struct{
charbase;
chartop;
int
stacksize;
}SqStack2;//操作符栈
2、栈类型
typedef
struct{
charbase;
chartop;
int
stacksize;
}Stack;
//栈类型
栈的基本操作设置如下：
void
InitStack（Stack
S.top=p;
S.size++;
Return
TRUE;
}
else
return
FALSE;
}
Status
Pop（Stack
else{
p=S.top;S.top=S.top->next;
e=p->:
data;S.size--;
return
TRUE;
}
}
3、运算代码
int
Operate（int
a,char
theta,int
b）
//计算表达式值：
主要是将大的表达式转化成小的表达式进行逐步求值
{
int
c;
if（theta==
+
）
c=a+b;
else
if（theta==
-
）
c=a-b;
else
if（theta==
）
c=a*b;
else
c=a/b;
return
c;
}//Operate
int
result（SqStack1OPND,SqStack2OPTR）
//求值
{
char
a=0;
char
theta;
int
b,c,number=0;
IntInitStack（OPND）;
CharInitStack（OPTR）;
CharPush（OPTR,#
）;
a=getchar（）;
while（a!
=
#
||
CharGetTop（OPTR）!
=
#
）
{
printf（“输入字符：
%c
“,a）;
if（!
In（a））//不是运算符则进栈
{
number=0;
while（!
In（a））
{
number
=
number*10
+（a-48）;//处理多位整数z=10*x+y
a
=
getchar（）;
}
IntPush（OPND,number）;
printf（“主要操作：
Push（OPND,%d）
“,number）;
}
else
switch（Precede（a,CharGetTop（OPTR）））
{
case
:
theta=CharPop（OPTR）;
c=IntPop（OPND）;
b=IntPop（OPND）;
IntPush（OPND,Operate（b,theta,c））;
printf（“主要操作：
Operate（%d,%c,%d）
“,b,theta,c）;
break;
}
printf（“OPND栈：
%d
OPTR栈：
%c/n“,IntGetTop（OPND）,CharGetTop（OPTR））;
}
printf（“The
result
is%d./n“,IntGetTop（OPND））;
//打印输出表达式值
return
OK;
}
4.主函数和其他函数的代码
void
main（）
//主函数，使用自定义函数完成功能
{
SqStack1
s1,*OPND;
SqStack2
s2,*OPTR;
OPND=
OPTR=
printf（“Please
enter
an
expression
with
a
end
of
#
./n“）;
printf（“The
Expression:
“）;
result（OPND,OPTR）;
}
char
Precede（char
a,char
b）//运算优先级判断
{
int
i,j;
char
Table[8][8]={,+,-,*,/,（,）,#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,（,,>,>,>,,>,>,#,#include
#include
#include
#define
STACK_INIT_SIZE
100
#define
STACKINCREMENT
10
#define
ERROR
0
#define
OK
1
//********************************************栈模块
typedef
struct
SqStack1//运算数栈
{
intbase;
inttop;
int
stacksize;
}SqStack1;
typedef
struct
SqStack2//运算符栈
{
charbase;
chartop;
int
stacksize;
}SqStack2;
void
IntInitStack（SqStack1S）
{
S->base=（int）malloc（STACK_INIT_SIZE*sizeof（int））;
if（!
S->base）
exit（ERROR）;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void
CharInitStack（SqStack2S）
{
S->base=（char）malloc（STACK_INIT_SIZE*sizeof（char））;
if（!
S->base）
exit（ERROR）;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int
IntGetTop（SqStack1S）
//取栈顶元素
{
int
e;
if（（*S）.top==（*S）.base）
return
0;
e=*（（*S）.top-1）;
return
e;
}
char
CharGetTop（SqStack2S）
//取栈顶元素
{
char
e;
if（（*S）.top==（*S）.base）
return
0;
e=*（（*S）.top-1）;
return
e;
}
int
IntPush（SqStack1S,int
e）
{（*S）.top++=e;
return
OK;
}
int
CharPush（SqStack2S,char
e）
{（*S）.top++=e;
return
OK;
}
int
IntPop（SqStack1S）
{
int
e;
if（（*S）.top==（*S）.base）
return
0;
e=*--（*S）.top;
return
e;
}
int
CharPop（SqStack2S）
{
char
e;
if（（*S）.top==（*S）.base）
return
0;
e=*--（*S）.top;
return
e;
}
//——————————————————*******************运算模块
char
Precede（char
a,char
b）//运算优先级判断
{
int
i,j;
char
Table[8][8]={,+,-,*,/,（,）,#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,（,,>,>,>,,>,>,#,:
theta=CharPop（OPTR）;
c=IntPop（OPND）;
b=IntPop（OPND）;
IntPush（OPND,Operate（b,theta,c））;
printf（“主要操作：
Operate（%d,%c,%d）
“,b,theta,c）;
break;
}
printf（“OPND栈：
%d
OPTR栈：
%c/n“,IntGetTop（OPND）,CharGetTop（OPTR））;
}
printf（“/n结果:
%d./n“,IntGetTop（OPND））;
//打印输出表达式值
return
OK;
}
//————————————————————————主程序模块
void
main（）
//主函数，使用自定义函数完成功能
{
SqStack1
s1,*OPND;
SqStack2
s2,*OPTR;
OPND=
OPTR=
printf（“请输入算数表达式并以
#
结尾./n“）;
printf（“算数表达式:
“）;
result（OPND,OPTR）;
}
升级会员 