数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文关键词：数据结构，算数，表达式，运算，演示
数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文简介：实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）
数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文内容：
实习报告
题目：设计一个演示用运算优先法对算数表达式求值过程的程序。
班级：
姓名：
学号：
完成日期：
一、
需求分析
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);
}
