数据结构 模拟计算器课程设计.docx
《数据结构 模拟计算器课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构 模拟计算器课程设计.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构模拟计算器课程设计
《数据结构》课程设计
实验报告
模拟计算器
班级：
学号：
姓名：
模拟计算器
1、问题描述
对于模拟计算器的设计，实际便是利用栈对一个表达式求值的问题。
要求：
对包含加，减，乘，除，括号的任意整型表达式进行求解
2、设计思路
表达式：
任何表达式都是由操作数、运算符和界限符组成的有意义的式子。
表达式求值时一般有后缀表示、中缀表示、前缀表示。
操作数：
可以是常数、变量、常量。
运算符：
从运算对象上分有单目运算符、双目运算符、三目运算符。
界限符：
左右括号和表达式结束符。
思路：
我们平时用到的表达式即为我们所输入的表达式（以‘#’结束），此表达式为中缀表达式，只要将此表达式利用栈来进出运算的符号转换为后缀表达式，之后利用栈来进出运算的数字将后缀表达式的值求出即可。
3、数据结构定义
一般表达式的长度不会过长所以将顺序栈的容量设为100已经算是比较大了
具体数据结构如下：
#definemaxsize100
typedefdoubledatatype1;
typedefchardatatype2;
typedefstructstack1
{
datatype1data1[maxsize];
inttop1;/*栈顶元素*/
}seqstack1,*pseqstack1;/*顺序栈*/
typedefstructstack2
{
datatype2data2[maxsize];
inttop2;/*栈顶元素*/
}seqstack2,*pseqstack2;/*顺序栈*/
4、系统功能模块介绍
（1）判断字符是否为操作数函数intisnum（char）
当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈，因此要判断表达式中的内容是操作数、运算符还是界限符，给出相关信息。
（2）求运算符优先级函数intpriority（char）
对输入的表达式中的内容，若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。
（3）中缀表达式转换为后缀表达式函数intinfix_exp_value（char*,char*）
我们平时使用的为中缀表达式，但若利用栈则利用后缀表达式比较容易计算，因此要将中缀表达式转换为后缀表达式，具体算法步骤如下：
<1>count=0，初始化运算符栈s，将结束符‘#’加入运算符栈s中。
<2>读表达式字符=>w。
<3>当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：
<3.1>如果w是操作数
判断若count==0
直接输出,读下一个字符=>w;转<3>。
若count!
=0
追加字符’@’,读下一个字符=>w,转<3>。
<3.2>w若是运算符，则：
count=1;
<3.2.1>如果栈顶为‘（’并且w为‘）’则‘（’出栈不输出，读下一个字
符=>w，转<3>。
<3.2.1>如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下
一个字符=>w，转<3>。
否则：
从运算符栈中出栈并输出，转<3>
（4）后缀表达式的求值函数doublepostfix_exp（char*）
使用一个操作数栈，当从左到右扫描表达式时，每遇到一个操作数就送入栈中保存，
如果操作数不止一位，则保存在operand中，遇到下一个操作数时，执行operand=operand*10+（ch-'0'），便可将操作数转化为数字。
每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时送入栈顶的值就是结果。
5、程序清单
#include
#include
#include
#definemaxsize100
typedefdoubledatatype1;
typedefchardatatype2;
typedefstructstack1
{
datatype1data1[maxsize];
inttop1;/*栈顶元素*/
}seqstack1,*pseqstack1;/*顺序栈*/
typedefstructstack2
{
datatype2data2[maxsize];
inttop2;/*栈顶元素*/
}seqstack2,*pseqstack2;/*顺序栈*/
/*栈的初始化*/
pseqstack1init_seqstack1（void）
{
pseqstack1S;
S=（pseqstack1）malloc（sizeof（pseqstack1））;
if（S）
S->top1=-1;
returnS;
}
pseqstack2init_seqstack2（void）
{
pseqstack2S;
S=（pseqstack2）malloc（sizeof（pseqstack2））;
if（S）
S->top2=-1;
returnS;
}
/*判断栈空*/
intempty_seqstack1（pseqstack1S）
{
if（S->top1==-1）
return1;
else
return0;
}
intempty_seqstack2（pseqstack2S）
{
if（S->top2==-1）
return1;
else
return0;
}
/*X入栈*/
intpush_seqstack1（pseqstack1S,datatype1X）
{
if（S->top1==maxsize-1）
{
printf（"栈满，无法入栈！
\n"）;
return0;
}
else
{
S->top1++;
S->data1[S->top1]=X;
return1;
}
}
intpush_seqstack2（pseqstack2S,datatype2X）
{
if（S->top2==maxsize-1）
{
printf（"栈满，无法入栈！
\n"）;
return0;
}
else
{
S->top2++;
S->data2[S->top2]=X;
return1;
}
}
/*X出栈*/
intpop_seqstack1（pseqstack1S,datatype1*X）
{
if（empty_seqstack1（S））
return0;
else
{
*X=S->data1[S->top1];
S->top1--;
return1;
}
}
intpop_seqstack2（pseqstack2S,datatype2*X）
{
if（empty_seqstack2（S））
return0;
else
{
*X=S->data2[S->top2];
S->top2--;
return1;
}
}
/*求栈顶元素*/
intgettop_seqstack1（pseqstack1S,datatype1*X）
{
if（empty_seqstack1（S））
return0;
else
*X=S->data1[S->top1];
return1;
}
intgettop_seqstack2（pseqstack2S,datatype2*X）
{
if（empty_seqstack2（S））
return0;
else
*X=S->data2[S->top2];
return1;
}
/*判断字符是否为操作数。
若是返回1，否则返回0*/
intisnum（charc）
{
if（c>='0'&&c<='9'）
return1;
else
return0;
}
/*求后缀表达式的值*/
doublepostfix_exp（char*A）
{
pseqstack1S;/*定义栈S*/
doubleoperand=0;
doubleresult;/*存放栈顶元素*/
doublea;/*运算符ch前的操作数出栈存入a*/
doubleb;/*运算符ch后的操作数出栈存入b*/
doublec;/*c==achb*/
charch;/*存放读取到的表达式（A）的字符*/
ch=*A++;/*读表达式字符=>A*/
S=init_seqstack1（）;/*初始化栈*/
while（ch!
='#'）/*遇到元素!
='#'时*/
{
if（isnum（ch））/*判断ch是否为数字字符,计算出操作数*/
operand=operand*10+（ch-'0'）;
else/*否则*/
{
if（operand）
{
push_seqstack1（S,operand）;/*当前字符不是数字,操作数结束,要入栈*/
operand=0;
}
if（ch!
='@'&&ch!
=''）
{
pop_seqstack1（S,&b）;/*运算符ch后的操作数出栈存入b*/
pop_seqstack1（S,&a）;/*运算符ch前的操作数出栈存入a*/
switch（ch）/*求achb==?
将结果赋给c*/
{
case'+':
c=a+b;
break;
case'-':
c=a-b;
break;
case'*':
c=a*b;
break;
case'/':
if（b!
=0）
c=a/b;
else
printf（"分母为零!
"）;
}
push_seqstack1（S,c）;/*将c压入栈中*/
}
}
ch=*A++;/*指针向下移动一位*/
}/*遇到'#'循环结束*/
gettop_seqstack1（S,&result）;/*此时栈顶元素即为计算结果result*/
returnresult;
}
/*优先级判断函数*/
intpriority（charop）
{
switch（op）
{
case'#':
return1;
case'）':
return2;
case'+':
case'-':
return3;
case'*':
case'/':
return4;
case'（':
return5;
default:
return0;
}
}
/*将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式*/
intinfix_exp_value（char*infixexp,char*postfixexp）
{
pseqstack2S;/*定义栈S*/
intcount=0;
charw;/*存放读取到的表达式（infixexp）的字符*/
charc;/*存放栈顶元素*/
chartopelement;/*存出栈元素*/
S=init_seqstack2（）;/*初始化栈*/
if（!
S）/*栈的初始化判断*/
{
printf（"栈初始化失败!
"）;
return0;
}
push_seqstack2（S,'#'）;/*将结束符'#'加入运算符栈S中*/
w=*infixexp;/*读表达式字符=>w*/
while（（gettop_seqstack2（S,&c）,c）!
='#'||w!
='#'）/*<3>栈顶元素不等于'#'或w不等于'#'时循环*/
{
if（isnum（w））/*判断w是否为操作数,若是直接输出,读下一个字符=>w,转<3>*/
{
if（count）
{
*postfixexp='@';
postfixexp++;
count=0;
}
*postfixexp=w;
postfixexp++;
w=*（++infixexp）;
}
else/*w若是运算符分类如下*/
{
count=1;
if（（gettop_seqstack2（S,&c）,c）=='（'&&w=='）'）
{/*如果栈顶为'（'并且w为'）'则'（'出栈不输出,读下一个字符=>w,转<3>*/
pop_seqstack2（S,&topelement）;/*将'（'出栈存入topelement*/
w=*（++infixexp）;
}
else
if（（gettop_seqstack2（S,&c）,c）=='（'||priority（（gettop_seqstack2（S,&c）,c））{/*如果栈顶为'（'或者栈顶优先级小于w优先级,则w入栈,读下一个字符=>w，转<3>*/
push_seqstack2（S,w）;
w=*（++infixexp）;
}
else/*否则*/
{/*从运算符栈中出栈并输出,转<3>*/
pop_seqstack2（S,&topelement）;
*postfixexp=topelement;
postfixexp++;
}
}
}
*postfixexp='#';/*在指针postfixexp指向的后缀表达式结尾追加字符'#'*/
*（++postfixexp）='\0';/*在指针postfixexp指向的后缀表达式最后追加结束符'\0'*/
return1;
}
/*主函数*/
intmain（）
{
inti=0;
charA[maxsize];
charB[maxsize];
printf（"请输入表达式,如:
11+22#,必须以#号结尾!
\n"）;
/*1+2*（9+7）-4/2#23+（（12*3-2）/4+34*5/7）+108/9#*/
A[i]=getchar（）;
while（A[i++]!
='#'）
{
A[i]=getchar（）;
}
A[i]='\0';
infix_exp_value（A,B）;
printf（"A==%s\n",A）;
printf（"B==%s\n",B）;
printf（"上式的结果为:
"）;
printf（"%g\n",postfix_exp（B））;
return0;
getch（）;
}
6、运行与调试分析等
（6.1）、运行与调试
（1）、先输入：
3+5*2#后按回车求值
，结果应为：
13
（2）、先输入：
1+2*（9+7）-4/2#后按回车求值，结果应为：
31
（3）、先输入：
15+3-2+（9/4）#后按回车求值，结果应为：
18.25
（4）、先输入：
1+3-2+（4*5/10）-2#后按回车求值，结果应为：
2
（5）、先输入：
23+（（12*3-2）/4+34*5/7）+108/9#后按回车求值，结果应为：
67.785714
（6.2）、分析
根据以上结果可以知道本程序正确，本程序中
intisnum（charc）
doublepostfix_exp（char*A）
intpriority（charop）
intinfix_exp_value（char*infixexp,char*postfixexp）
等函数原型为课本P64—P68的函数，单元函数只能对0-9之间的数进行基本的算术运算，无法对大于9的数进行运算，因而对函数doublepostfix_exp（char*A）与intinfix_exp_value（char*infixexp,char*postfixexp）进行一定的修改，便可以运算整形数字，
（6.2.1）
函数doublepostfix_exp（char*A）
修改前后对比
修改前
修改后
（6.2.2）
函数intinfix_exp_value（char*infixexp,char*postfixexp）
修改前后对比
修改前
修改后
欢迎您的下载，
资料仅供参考！
致力为企业和个人提供合同协议，策划案计划书，学习资料等等
打造全网一站式需求
升级会员 