(一> 需求分析
1、输入地形式和输入值地范围:
根据题目要求与提示,先选择你要使用地表达式形式<中缀用1,后缀用0),在输入一个中缀表达式,输入数地范围为int型,此时,程序将计算出表达式地结果.
2、输出地形式:当按照程序要求选择了1或0之后,再输入表达式;如果选择地是1,则程序将自动运算出表达式结果;如果之前选择地是0,则程序将现将中缀表达式转化为后缀表达式并计算出结果.
3、程序所能达到地功能:
本程序能计算出含+、-、*、/、<、)等运算符地简单运算.
4、测试数据:
输入一个表达式,如果你之前选择地是“中缀表达式”,那么输入5*(4-2>#,那么输出结果是10;如果之前选择地是“后缀表达式”,那么输入5*<4-2)#,那么他将先转换成后缀表达式5 4 2 - * #,再输出结果10.
如果输入表达式没有结束标示符#,如5*<4-2),那将不会输出任何结果,或出现错误结果.
(二> 概要设计
为了实现上述操作,应以栈为存储结构.
1.基本操作:
<1). int GetTop(SqStack *s>
初始条件:栈存在;
操作结果:若栈为空,则返回s地栈顶元素;否则返回ERROR.
<2).void Push(SqStack *s,int e>
初始条件:栈存在;
操作结果:插入e为新地栈顶元素.
<3).int Pop(SqStack *s>
初始条件:栈存在;
操作结果:若栈不空,则删除之,并返回其值;否则返回REEOR.
<4).void InitStack(SqStack *s>
初始条件:栈存在;
操作结果:置栈为空.
<5).int Empty(SqStack *s>
初始条件:栈存在;
操作结果:判定s是否为空栈.
<6).int Operate(int a,char theta, int b>
初始条件:操作数a和b存在,且theta是+、-、*、/四则运算;
操作结果:返回a与b间theta运算地结果.
<7).int In(char s,char* TestOp>
初始条件:s为待判断字符,TestOp为已知地算符集合;
操作结果:s为算符集合中地元素则返回1,否则返回0.
<8).int ReturnOpOrd(char op,char* TestOp>
初始条件:op为待确定运算符,TestOp为已知地算符集合;
操作结果:确定运算符类型.
<9).char precede(char a, char b>
初始条件:a、b存在;
操作结果:返回算符a和b地优先权高低.
<10).void PrintOpnd(SqStack *s>
初始条件:栈存在;
操作结果:输出运算数栈.
<11).void PrintOptr(SqStack *s>
初始条件:栈存在;
操作结果:输出运算符栈.
<12).void Store(char *s,char ch>
初始条件:字符数组 s存在,字符ch已知;
操作结果:将ch存入数组s.
<13).void Change(char *s1,char *s2>
初始条件。重罪表达式s1已知;
操作结果:将中缀表达式s1转为后缀表达式s2.
2.本程序包含二个模块:
<1)主程序模块;
<2)中缀表达式求值模块以及中缀表达式转换为后缀表达式并求值模块<3)模块调用图:
主程序模块
中缀表达式求值模块中缀表达式转换为后缀表达式并求值模块
(三> 详细设计
1.存储类型,元素类型,结点类型:
typedef struct{ //定义栈
int data[SIZE]。
int top。
int base。
}SqStack。
char OPSET[7]={'+' , '-' , '*' , '/' ,'(' , '>' , '#'}。
//定义OPSET字符数组为算符集合
char Prior[7][7] = {
// 算符间地优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
}。
2.每个模块地分析:
<1)主程序模块:
int main(>{
char s=0,c。
while(1>{
printf("请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式)\n">。
c=getchar(>。
fflush(stdin>。
if(c=='1'>{//中缀表达式运算结果
printf("%d\n",EvaluateExpression_1(>>。
}
else{//后缀表达式运算结果
printf("%d\n",EvaluateExpression_2(>>。
}
do{
scanf("%c",&s>。
if(s=='q'||s=='Q'>
exit(0>。
}
while(s!='\n'>。
system("cls">。
}
return 0。
}
<2)int EvaluateExpression_1(>{
//中缀求值
SqStack OPND,OPTR。
char ch,theta,exp[100]={0}。
int i=0,s=0,a=0,b=0,step=0。
InitStack(&OPND>。
InitStack(&OPTR>。
Push(&OPTR,'#'>。
gets(exp>。
ch=exp[0]。
while(ch!='#'||GetTop(&OPTR>!='#'>{
if(!In(ch,OPSET>>{//不是运算符则进栈
if(In(exp[i+1],OPSET>>{//未出现连续数字
Push(&OPND,ch-48>。
ch=exp[++i]。
}//if
else//出现连续数字
{
s=exp[i++]-48。
while(exp[i]>='0'&&exp[i]<='9'>{
s=s*10+exp[i++]-48。
}
Push(&OPND,s>。
s=0。
ch=exp[i]。
}
}
else
switch(precede(GetTop(&OPTR>,ch>>{
case '<'://栈顶元素优先权低
Push(&OPTR,ch>。
ch=exp[++i]。
break。
case '='://脱括号并接受下一字符
Pop(&OPTR>。
ch=exp[++i]。
break。
case '>'://退栈并将运算结果入栈
theta=Pop(&OPTR>。
b=Pop(&OPND>。
a=Pop(&OPND>。
Push(&OPND,Operate(a,theta,b>>。
break。
}//switch
}//while
return GetTop(&OPND>。
}//EvaluateExpression_1
int EvaluateExpression_2(>{//后缀求值
SqStack OPND。
char ch,theta,receive[100]={0},exp[100]={0}。
int i=0,s=0,a=0,b=0,step=0。
InitStack(&OPND>。
printf("请输入一个中缀表达式:\n">。
gets(receive>。//输入中缀表达式
Change(receive,exp>。
printf("相应地后缀表达式为:\n">。
puts(exp>。//输出对应地后缀表达式
ch=exp[0]。
while(ch!='#'>{
if(!In(ch,OPSET>>{//不是运算符则压入栈中
if(exp[i+1]==' '>{//未出现连续数字
Push(&OPND,ch-48>。
i+=2。
ch=exp[i]。
}//if
else//出现连续数字
{
s=exp[i++]-48。
while(exp[i]>='0'&&exp[i]<='9'>{
s=s*10+exp[i++]-48。
}//while
Push(&OPND,s>。
s=0。
ch=exp[++i]。
}//else
}//if
else{
theta=ch。
b=Pop(&OPND>。
a=Pop(&OPND>。
Push(&OPND,Operate(a,theta,b>>。
i+=2。
ch=exp[i]。
}
}
return GetTop(&OPND>。
}//EvaluateExpression_2<
3)函数调用关系图
3.完整地程序:
#include"stdio.h"
#include"stdlib.h"
#define SIZE 80
#define OK 1
#define ERROR 0
typedef struct{ //定义栈
int data[SIZE]。
int top。
int base。
}SqStack。
char OPSET[7]={'+' , '-' , '*' , '/' ,'(' , '>' , '#'}。
//定义OPSET字符数组为算符集合
char Prior[7][7] = {
// 算符间地优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
}。
int GetTop(SqStack *s>{
//若栈为空,则返回s地栈顶元素;否则返回ERROR
if(s->top==s->base>
return ERROR。
return (s->data[s->top-1]>。
}
void Push(SqStack *s,int e>{
//插入e为新地栈顶元素
s->data[s->top]=e。
s->top++。
}
int Pop(SqStack *s>{
//若栈不空,则删除之,并返回其值;否则返回REEOR
int e。
if(s->base==s->top>
return ERROR。
else{
e=s->data[s->top-1]。
s->top--。
}
return e。
}
void InitStack(SqStack *s>{
//置栈S为空
s->top=0。
s->base=0。
}
int Empty(SqStack *s>{
//判定s是否为空栈
if(s->base==s->top>
return 1。
else
return 0。
}
int Operate(int a,char theta, int b> {
//返回a与b间theta运算地结果
switch(theta> {
case '+': return a+b。break。
case '-': return a-b。break。
case '*': return a*b。break。
case '/': return a/b。break。
default : return 0。
}
}
int In(char s,char* TestOp> {
//s为待判断字符,TestOp为已知地算符集合
int Find=0。
for (int i=0。 i<7。 i++> {
if (s == TestOp[i]> Find= 1。
}
return Find。
}
int ReturnOpOrd(char op,char* TestOp> {
//确定运算符类型,op为待确定运算符,TestOp为已知地算符集合 int i。
for(i=0。 i<7。 i++> {
if (op == TestOp[i]> return i。
}
return 0。
}
char precede(char a, char b> {
//返回算符a和b地优先权高低
return Prior[ReturnOpOrd(a,OPSET>][ReturnOpOrd(b,OPSET>]。
}
void PrintOpnd(SqStack *s>{
//输出运算数栈
int i=s->base。
printf("Stack OPND:">。
if(!Empty(s>>{
for(。i<(s->top>。i++>
printf(" %d ",s->data[i]>。
}
else
printf(" ">。
printf("\n">。
}
void PrintOptr(SqStack *s>{
//输出运算符栈
int i=s->base。
printf("Stack OPTR:">。
for(。i<(s->top>。i++>
printf(" %c ",s->data[i]>。
printf("\n">。
}
void Store(char *s,char ch>{
//将ch存入数组s
char *p=s。
while(*p>{
p++。
}
*p++=ch。
}
int EvaluateExpression_1(>{
//中缀求值
SqStack OPND,OPTR。
char ch,theta,exp[100]={0}。
int i=0,s=0,a=0,b=0,step=0。
InitStack(&OPND>。
InitStack(&OPTR>。
Push(&OPTR,'#'>。
gets(exp>。
ch=exp[0]。
while(ch!='#'||GetTop(&OPTR>!='#'>{
if(!In(ch,OPSET>>{//不是运算符则进栈
if(In(exp[i+1],OPSET>>{//未出现连续数字
Push(&OPND,ch-48>。
ch=exp[++i]。
}//if
else//出现连续数字
{
s=exp[i++]-48。
while(exp[i]>='0'&&exp[i]<='9'>{
s=s*10+exp[i++]-48。
}
Push(&OPND,s>。
s=0。
ch=exp[i]。
}
}
else
switch(precede(GetTop(&OPTR>,ch>>{
case '<'://栈顶元素优先权低
Push(&OPTR,ch>。
ch=exp[++i]。
break。
case '='://脱括号并接受下一字符
Pop(&OPTR>。
ch=exp[++i]。
break。
case '>'://退栈并将运算结果入栈
theta=Pop(&OPTR>。
b=Pop(&OPND>。
a=Pop(&OPND>。
Push(&OPND,Operate(a,theta,b>>。
break。
}//switch
}//while
return GetTop(&OPND>。
}//EvaluateExpression_1
void Change(char *s1,char *s2>{
//将中缀表达式转为后缀表达式
SqStack OPTR。
char ch。
int i=0,sum=0。
InitStack(&OPTR>。
Push(&OPTR,'#'>。
ch=s1[0]。
while(ch!='#'||GetTop(&OPTR>!='#'>{
if(!In(ch,OPSET>>{//不是运算符则进栈
if(In(s1[i+1],OPSET>>{//未出现连续数字
Store(s2,ch>。
Store(s2,' '>。//存入一个空格
ch=s1[++i]。
}//if
else//出现连续数字
{
while(s1[i]>='0'&&s1[i]<='9'>{
Store(s2,s1[i]>。
i++。
}//while
Store(s2,' '>。//存入一个空格
ch=s1[i]。
}//else
}//if
else
switch(precede(GetTop(&OPTR>,ch>>{
case '<'://栈顶元素优先权低
Push(&OPTR,ch>。
ch=s1[++i]。
break。
case '='://脱括号并接受下一字符
Pop(&OPTR>。
ch=s1[++i]。
break。
case '>'://退栈并将运算结果入栈
Store(s2,Pop(&OPTR>>。
Store(s2,' '>。//补入一个空格作为间隔
break。
}//switch
}//while
Store(s2,ch>。
}//Change
int EvaluateExpression_2(>{//后缀求值
SqStack OPND。
char ch,theta,receive[100]={0},exp[100]={0}。
int i=0,s=0,a=0,b=0,step=0。
InitStack(&OPND>。
printf("请输入一个中缀表达式:\n">。
gets(receive>。//输入中缀表达式
Change(receive,exp>。
printf("相应地后缀表达式为:\n">。
puts(exp>。//输出对应地后缀表达式
ch=exp[0]。
while(ch!='#'>{
if(!In(ch,OPSET>>{//不是运算符则压入栈中
if(exp[i+1]==' '>{//未出现连续数字
Push(&OPND,ch-48>。
i+=2。
ch=exp[i]。
}//if
else//出现连续数字
{
s=exp[i++]-48。
while(exp[i]>='0'&&exp[i]<='9'>{
s=s*10+exp[i++]-48。
}//while
Push(&OPND,s>。
s=0。
ch=exp[++i]。
}//else
}//if
else{
theta=ch。
b=Pop(&OPND>。
a=Pop(&OPND>。
Push(&OPND,Operate(a,theta,b>>。
i+=2。
ch=exp[i]。
}
}
return GetTop(&OPND>。
}//EvaluateExpression_2
int main(>{
char s=0,c。
while(1>{
printf("请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式)\n">。
c=getchar(>。
fflush(stdin>。
if(c=='1'>{//中缀表达式运算结果
printf("%d\n",EvaluateExpression_1(>>。
}
else{//后缀表达式运算结果
printf("%d\n",EvaluateExpression_2(>>。
}
do{
scanf("%c",&s>。
if(s=='q'||s=='Q'>
exit(0>。
}
while(s!='\n'>。
system("cls">。
}
return 0。
}(四> 程序使用说明及测试结果
1.程序使用说明
<1)本程序地运行环境为VC6.0.
<2)进入演示程序后即显示提示信息:
请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式):
若输入1,则继续输入一中缀表达式,程序将计算出结果;
若输入0,则程序将继续提示:
请输入一个中缀表达式:
输入一中缀表达式
相应地后缀表达式为:
程序此后将显示转换后地后缀表达式,并输出结果.
2.测试结果:
例如:5*<6-4)#,输出结果为10.
3.调试中地错误及解决办法.(遇到时给出>
开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法,最终得出程序.
4.运行界面
先输入1,再输入表达式5*<6-4)#
先输入0,再输入表达式5*<6-4)#
<五)、实验总结(实验心得>
你在编程过程中花时多少?
零散地时间全部加上,大概有十多个小时.
多少时间在纸上设计?
没有在纸上设计.
多少时间上机输入和调试?
十来个小时.
多少时间在思考问题?
不知道,一两个吧.
遇到了哪些难题?
开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法,最终得出程序.
你是怎么克服地?
克服困难地方法只要是看书查质料,向同学请教,并耐心对程序进行单步调试.
你地收获有哪些?
这次实验我感觉难度很大,花费地时间比较长,但是对我了解要学习数据结构帮助很大.
教师评语:
实验成绩:
指导教师签名:
批阅日期: