数据结构 模拟计算器课程设计
《数据结构》课程设计
实验报告
模拟计算器
班 级:
学 号:
姓 名:
模拟计算器
1、 问题描述
对于模拟计算器的设计,实际便是利用栈对一个表达式求值的问题。
要求:
对包含加,减,乘,除,括号的任意整型表达式进行求解
2、 设计思路
表达式:任何表达式都是由操作数、运算符和界限符组成的有意义的式子。
表达式求值时一般有后缀表示、中缀表示、前缀表示。
操作数:可以是常数、变量、常量。
运算符:从运算对象上分有单目运算符、双目运算符、三目运算符。
界限符:左右括号和表达式结束符。
思 路:我们平时用到的表达式即为我们所...
《数据结构》课程设计
实验报告
模拟计算器
班 级:
学 号:
姓 名:
模拟计算器
1、 问题描述
对于模拟计算器的设计,实际便是利用栈对一个
达式求值的问题。
要求:
对包含加,减,乘,除,括号的任意整型表达式进行求解
2、 设计思路
表达式:任何表达式都是由操作数、运算符和界限符组成的有意义的式子。
表达式求值时一般有后缀表示、中缀表示、前缀表示。
操作数:可以是常数、变量、常量。
运算符:从运算对象上分有单目运算符、双目运算符、三目运算符。
界限符:左右括号和表达式结束符。
思 路:我们平时用到的表达式即为我们所输入的表达式(以‘ # ’结束),此表达式为中缀表达式,只要将此表达式利用栈来进出运算的符号转换为后缀表达式,之后利用栈来进出运算的数字将后缀表达式的值求出即可。
3、 数据结构定义
一般表达式的长度不会过长所以将顺序栈的容量设为100已经算是比较大了
具体数据结构如下:
# define maxsize 100
typedef double datatype1;
typedef char datatype2;
typedef struct stack1
{
datatype1 data1[maxsize];
int top1; /*栈顶元素*/
}seqstack1,*pseqstack1; /*顺序栈*/
typedef struct stack2
{
datatype2 data2[maxsize];
int top2; /*栈顶元素*/
}seqstack2,*pseqstack2; /*顺序栈*/
4、 系统功能模块介绍
(1) 判断字符是否为操作数
数 int isnum(char)
当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈,因此要判断表达式中的内容是操作数、运算符还是界限符,给出相关信息。
(2) 求运算符优先级函数 int priority(char )
对输入的表达式中的内容,若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。
(3) 中缀表达式转换为后缀表达式函数 int infix_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) 后缀表达式的求值函数 double postfix_exp(char *)
使用一个操作数栈,当从左到右扫描表达式时,每遇到一个操作数就送入栈中保存,
如果操作数不止一位,则保存在operand中,遇到下一个操作数时,执行operand=operand*10+(ch-'0'),便可将操作数转化为数字。每遇到一个运算符就从栈中取出两个操作数进行当前的计算,然后把结果在入栈,直到整个表达式结束,这时送入栈顶的值就是结果。
5、 程序
# include
# include
# include
# define maxsize 100
typedef double datatype1;
typedef char datatype2;
typedef struct stack1
{
datatype1 data1[maxsize];
int top1; /*栈顶元素*/
}seqstack1,*pseqstack1; /*顺序栈*/
typedef struct stack2
{
datatype2 data2[maxsize];
int top2; /*栈顶元素*/
}seqstack2,*pseqstack2; /*顺序栈*/
/*栈的初始化*/
pseqstack1 init_seqstack1(void)
{
pseqstack1 S;
S=(pseqstack1)malloc(sizeof(pseqstack1));
if(S)
S->top1=-1;
return S;
}
pseqstack2 init_seqstack2(void)
{
pseqstack2 S;
S=(pseqstack2)malloc(sizeof(pseqstack2));
if(S)
S->top2=-1;
return S;
}
/*判断栈空*/
int empty_seqstack1(pseqstack1 S)
{
if(S->top1==-1)
return 1;
else
return 0;
}
int empty_seqstack2(pseqstack2 S)
{
if(S->top2==-1)
return 1;
else
return 0;
}
/*X入栈*/
int push_seqstack1(pseqstack1 S,datatype1 X)
{
if(S->top1==maxsize-1)
{
printf("栈满,无法入栈!\n");
return 0;
}
else
{
S->top1++;
S->data1[S->top1]=X;
return 1;
}
}
int push_seqstack2(pseqstack2 S,datatype2 X)
{
if(S->top2==maxsize-1)
{
printf("栈满,无法入栈!\n");
return 0;
}
else
{
S->top2++;
S->data2[S->top2]=X;
return 1;
}
}
/*X出栈*/
int pop_seqstack1(pseqstack1 S,datatype1 *X)
{
if(empty_seqstack1(S))
return 0;
else
{
*X=S->data1[S->top1];
S->top1--;
return 1;
}
}
int pop_seqstack2(pseqstack2 S,datatype2 *X)
{
if(empty_seqstack2(S))
return 0;
else
{
*X=S->data2[S->top2];
S->top2--;
return 1;
}
}
/*求栈顶元素*/
int gettop_seqstack1(pseqstack1 S,datatype1 *X)
{
if(empty_seqstack1(S))
return 0;
else
*X=S->data1[S->top1];
return 1;
}
int gettop_seqstack2(pseqstack2 S,datatype2 *X)
{
if(empty_seqstack2(S))
return 0;
else
*X=S->data2[S->top2];
return 1;
}
/*判断字符是否为操作数。若是返回1,否则返回0*/
int isnum(char c)
{
if(c>='0' && c<='9')
return 1;
else
return 0;
}
/*求后缀表达式的值*/
double postfix_exp(char *A)
{
pseqstack1 S; /*定义栈S*/
double operand=0;
double result; /*存放栈顶元素*/
double a; /*运算符ch前的操作数出栈存入a*/
double b; /*运算符ch后的操作数出栈存入b*/
double c; /*c==a ch b*/
char ch; /*存放读取到的表达式(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*/
本文档为【数据结构 模拟计算器课程设计】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。