算数表达式的求解课程设计报告算数表达式的求解课程设计报告
合肥学院
计算机科学与技术系
课程设计报告
20 12 ,20 13 学年第 2 学期
课程 数据结构与算法 课程设计名称 算数表达式的求解 学生姓名 周丽娟 学号 1104012013 专业班级 11计本3班 指导教师 李红
20 13 年 3 月
【问题描述】
(算数表达式的求解)给定一个算数表达式,通过程序求出最后的结果。 【要求】
1、从键盘输入要求解的算术表达式;
2、采用栈结构进行算数表达式的求解过程;
3、能够判断算数表达式的正确与否;
4、对于错误表达式给出...
算数表达式的求解课程
合肥学院
计算机科学与技术系
课程设计报告
20 12 ,20 13 学年第 2 学期
课程 数据结构与算法 课程设计名称 算数表达式的求解 学生姓名 周丽娟 学号 1104012013 专业班级 11计本3班 指导教师 李红
20 13 年 3 月
【问题描述】
(算数表达式的求解)给定一个算数表达式,通过程序求出最后的结果。 【要求】
1、从键盘输入要求解的算术表达式;
2、采用栈结构进行算数表达式的求解过程;
3、能够判断算数表达式的正确与否;
4、对于错误表达式给出提示;
5、对于正确表达时给出最后的结果。
1、问题分析和任务定义
有题目可知,程序要求给定一算数表达式并计算最后的结果,我们知道,在高级语言中,任何一个表达式都是有操作数、运算符和界限符组成。在计算过程中,还要考虑表达式中有无括号以及左右括号之分。由于运算符有优先级的高低,因此一个算数表达是不可能总是按顺序执行。
通过以上可知,可以用栈来实现运算符的优先级完成算术表达式的求解。 为实现算法的优先级,设置两个栈:一个称为操作数栈opnd,用以寄存操作数和运算结果,另一个为操作符栈optr,用以寄存运算符。
该算法的基本思想是:
(1)首先置操作数栈opnd为空栈,表达式结束符“#”为操作符栈optr的栈底元素。 (2)依次读入表达式中每个字符,若为操作数,则进opnd栈;若是运算符,则与optr栈的栈顶运算符比较优先级后做相应操作:若当前操作符大于optr栈的栈顶,则当前操作符入栈;否则,opnd栈的栈顶元素、次栈顶元素出栈,同时optr栈的栈顶元素也出栈,形成运算,并将结果压入opnd栈,直至整个表达式求值完毕(即optr栈的栈顶元素和当前读入的字符均为“#”)。
对于算术表达式的输入,本程序采用gets()的
读入,将运算符‘+’,‘-’,‘*’,‘/’,‘(’,‘)’,‘#’存储在数组中时,定义表达式求解函数,在函数中判断读入的字符,如果是运算符,将这些字符入操作符optr栈,并比较优先级,判断是否运算。若读入的字符为‘0’到‘9’之间的数字时,用字符相减转化为整型,然后将转化后的整型再转化为ASCII的形式压入操作数栈opnd中。
2、数据结构的选择和概要设计
(1)存储结构设计
本程序主要采用顺序栈结构类型(Stack)来存储表达式计算中的数据。程序中需要建立两个栈,一个栈用于寄存运算符,另一个则用于寄存操作数和计算结果,故需要建立两个顺序栈结构类型。
(2)算数优先级设计
对一任意的表达式,由于表达式中运算符的优先级不同,可能会使表达式不按顺序进行计算。在本程序中定义函数Proceed()来比较运算符的优先级,而函数中各优先级的比较主要根据以下优先级比较的表格:
表1:运算符优先级
运算符 + - * / ( ) # 用数字表示 0 1 2 3 4 5 6 栈内操作符的优先级 3 3 5 5 1 6 0 栈外操作符的优先级 2 2 4 4 6 1 0
在Precede()函数中定义两个字符型参数变量op和c,其中op表示栈顶运算符,c表示当前读入运算符,对于当前运算符是否入栈,进行如下操作:
比较当前运算符和栈顶运算符的优先级的大小:
1、如果当前运算符的优先级大于栈顶运算符的优先级,即op
c;令函数返回值为'>',此时应将栈顶运算符出栈和栈顶、次栈顶操作数出栈并进行相应的运算。
3、如果当前元素的优先级等于栈顶运算符的优先级,即op=c;令函数的返回值为'=',此时界限符内的表达式已计算完毕。
(3)程序模块设计
1)程序模块
本程序主要包含3个模块:主程序模块、计算模块以及顺序栈操作模块,调用关系如图所示:
顺序栈操作模块 计算模块主程序模块
图1:程序模块图
2)系统功能模块
本程序大致包含10个函数,其中包含主函数。每个函数都有其相对应的功能实现。
1操作符的输入函数 int In(char c); ?
2运算符比较优先级函数 char Proceed(char op,char c); ?
3进行四则运算函数 int Operate(int a,char a1,int b); ?
4实现表达式的求值函数 int EvalExpres(void); ?
5初始化栈函数 void InitStack(Stack *s); ?
6入栈函数 void Push(Stack *s, int x); ?
7出栈函数 int Pop(Stack *s); ?
8取栈顶元素函数 int GetTop(Stack *s) ; ?
9判栈空函数 void Empty(Stack *s); ?
10主函数 int main() ?
3)函数之间主要调用的关系图
本程序主要包含10个程序,各程序之间的关系如图所示:(部分函数用以上的编号表示)
Void main()
Int EvalExpres(void)
1 2 3 5 6 7 8 9 ????????
图2:函数之间调用关系图
3、详细设计和编码
(1)、结构体类型的定义
typedef struct
{
int data[MAXSIZE];
int top;
int base; //栈底
}Stack;
(2)、全局变量定义
//以下为函数声明
void InitStack(Stack *); //初始化栈
int Empty(Stack *); //判空栈
void Push(Stack *, int ); //进栈
int Pop(Stack *);//出栈
int GetTop(Stack *); //取栈顶元素
int Operate(int ,char ,int ); // 计算结果
char Proceed(char ,char ); // 比较优先级
int In(char ); //判断输入符
int EvalExpres(void); //表达式计算函数 // 定义两个栈分别存放运算符和操作数 Stack StackR,StackD; (3)、系统主要子程序的详细设计
1)、主函数模块设计
int main()//主函数
{
int v;
char ch;
while(1)
{
printf("\t************欢迎使用算术表达式的求解的小程序************\n");
v = EvalExpres();
printf("\t表达式的计算结果为:%d",v);
printf("\n\tInput 'n' to quit and ENTER run again:");
do
{
scanf("%c",&ch);
if(ch == 'n' || ch == 'N')
exit(0);
}while(ch!='\n');
system("cls");
}
return 0;
}
在主函数中,设定用户操作界面的形式,通过调用表达式求解的子函数实现算法所要实现的功能,然后通过while()循环语句控制,可以实现多次调试。
2)、计算函数模块
int Operate(int a,char a1,int b) {
int s;
int d1 = a;
int d2 = b; //把字符ab变为对应数字
switch(a1)
{
case '+':
s = d1+d2;
break;
case '-':
s = d2-d1;
break;
case '*':
s = d1*d2;
break;
case '/':
s = d2/d1;
}
return (s+'0'); //将运算结果转化为ascii码的形式入栈, }
在计算函数中,定义3个变量,表示基本运算中的变量。采用开关语句实现表达式的基本运算,将运算结果转化为ASCII的形式返回。
3)、表达式求解的函数模块
int EvalExpres(void) // 表达式求解函数
{
int a,b,i=0,s=0;
char c[80],r;
InitStack(&StackR); //初始化栈
Push(&StackR,'#'); //将表达式起始符压入栈
InitStack(&StackD);
printf(" \t请输入表达式并以‘#’结束:");
gets(c);
while(c[i]!='#' || GetTop(&StackR)!='#')
{
if(!In(c[i])) //判断读入的字符是不是运算符 不是则进opnd栈
{ if(c[i] >= '0' && c[i] <= '9')
{
s += c[i]-'0'; //字符的ascii相减将字符型转化为整型
while(!In(c[++i])) //继续判断下一个字符,若不是运算符,表明为多位数,直到读取到字符为运算符为止
{
s*=10;
s += c[i]-'0';
}
Push(&StackD,s+'0'); //将整型转化为ascii的形式入栈,使字符在栈内以ascii的形式保存,实现多位数的计算
s = 0; //初始化s,继续判断
}
else
{
printf("你输入的表达式有误!\n");
return 0;
}
}
else
switch(Proceed(GetTop(&StackR),c[i])) //此函数用来比较读取的运算符和栈顶运算符的优先级
{
case '<': //栈顶的元素优先级低,当前运算符入栈
Push(&StackR,c[i]);
i++;
break;
case '=':
Pop(&StackR);
i++;
break;
case '>': //栈顶的优先级高则出栈,并将计算结果压入栈内
r = Pop(&StackR);
a = Pop(&StackD)-'0'; //操作数在栈内以ascii的形式存储,出站后要将
ascii转化为整型,然后进行运算
b = Pop(&StackD)-'0';
Push(&StackD,Operate(a,r,b)) ;
break;
}
}
return (GetTop(&StackD)-'0'); // 将栈顶元素转化为整型的形式输出
}
对于表达式求解函数,在程序中主要思想是对读入的表达式进栈进行判断。若读入的是‘0’到‘9’之间的字符,将这些字符采用ascii相减的形式转化为整型,再入opnd栈,若读入的字符为运算符,则将运算符入栈,并比较运算符之间的优先级,看是否运算,若栈顶的运算符小于当前输入的运算符,则不需运算,只要将当前运算符入栈即可。否则,运算。运算时先将optr栈的栈顶运算符和opnd栈的栈顶、次栈顶元素出栈,并将opnd栈中出栈的元素的ASCII形式转化为整型再计算,最后讲计算结果再转化为ASCII码的形式压入opnd栈中。使表达式求解函数返回值为opnd的栈顶元素。
4、上级调试过程
遇到问题以及解决
问题1、调试时没有错误,但运行时显示错误。
解决方案:通过它提示的错误和警告,在判断是否为运算符的子函数中出现错误,如果为运算符时返回1,其次返回0,在返回0时没有用else,这样使得整个子函数可以返回一个有效值。
问题2、调试时程序显示没有错误,可以运行,但在运行时结果却出现错误。 解决方案:把程序从头看了一遍,发现在比较优先级的函数中,优先级的比较比较乱,而且部分出错,后来查了关于运算符优先级的,通过在纸上把各种优先级列出,解决这个错误。
算法的时间复杂度
由于在主函数用到嵌套循环,故算法的时间复杂度为O(n^2)。
5、测试结果及其分析
(1)、实现基本的加减乘除运算,当想要继续输入表达式时点击enter键,若要结束,点击n或N键即可,而且可实现多位数的运算。
(2)、实现复杂的算术表达式
(3)、错误表达式的处理
6、用户使用说明
(1)本程序执行的文件为“算数表达式的求解问题”。
(2)所求表达式中都只是仅包含加、减、乘、除4种基本运算的,其中也包含括号的应用,所有的运算对象均为简单变量,要求将表达式中的数字字符转化为整型,且输入表达式以“#”结束。
(3)输入表达式时,以‘#’结束,当点击回车键时即可得到运算结果,当想继续输入表达式时,再次点击回车键即可,当想结束时,点击字母‘n’或‘N’。
(4)当输入错误表达式时,程序会给出相应的提醒。
7、参考文献
(1)王昆仑 、李红主编,数据结构与算法,北京:中国铁道出版社,2007年5月
(2)阮宏一 、鲁静主编,数据结构课程设计(C/C++描述),北京:电子工业出版社,2011年1月
8、附录(源程序):
#include
#include
#define MAXSIZE 16
typedef struct
{
int data[MAXSIZE];
int top;
int base; //栈低
}Stack; // 顺序栈的定义
//以下为函数声明
void InitStack(Stack *); //初始化栈
int Empty(Stack *); //判空栈
void Push(Stack *, int ); //进栈
int Pop(Stack *);//出栈
int GetTop(Stack *); //取栈顶元素
int Operate(int ,char ,int ); // 计算结果
char Proceed(char ,char ); // 比较优先级
int In(char ); //判断输入符
int EvalExpres(void); //表达式计算函数 // 定义两个栈分别存放运算符和操作数
Stack StackR,StackD;
int main()//主函数
{
int v;
char ch;
while(1)
{
printf("\t************欢迎使用算术表达式的求解的小程序************\n");
v = EvalExpres();
printf("\t表达式的计算结果为:%d",v);
printf("\n\tInput 'n' to quit and ENTER run again:");
do
{
scanf("%c",&ch);
if(ch == 'n' || ch == 'N')
exit(0);
}while(ch!='\n');
system("cls");
}
return 0;
}
void InitStack(Stack *s) //初始化栈
{
s->top = 0;
s->base = 0;
}
int Empty(Stack *s)//判断栈是否为空
{
if(s->top ==s->base)
return 1; //栈空时返回1,否则返回0
else
return 0;
}
void Push(Stack *s, int x) // 进栈
{
if(s->top == MAXSIZE)
{
printf("\terror!\n");
exit(0);
}
else
{
s->data[s->top] = x;
s->top++;
}
}
int Pop(Stack *s)// 出栈
{
int e;
if(Empty(s))
{
printf("\terror!\n");
exit(0);
}
else
{
s->top--;
e = s->data[s->top];
return e;
}
}
int GetTop(Stack *s) //取栈顶元素
{
if(Empty(s))
{
printf("\terror!\n");
exit(0);
}
else
return s->data[s->top-1];
}
int EvalExpres(void) // 表达式求解函数
{
int a,b,i=0,s=0;
char c[80],r;
InitStack(&StackR);
Push(&StackR,'#');
InitStack(&StackD);
printf(" \t请输入表达式并以‘#’结束:");
gets(c);
while(c[i]!='#' || GetTop(&StackR)!='#')
{
if(!In(c[i])) //判断读入的字符不是运算符 是则进栈
{ if(c[i] >= '0' && c[i] <= '9')
{
s += c[i]-'0'; //字符相减将字符型转化为整型
while(!In(c[++i])) //继续判断下一个字符,若不是运算符,表明为多位数,直到读取到字符为运算符为止
{
s*=10;
s += c[i]-'0';
}
Push(&StackD,s+'0'); //将整型转化为ascii的形式入栈,使字符在栈内以ascii的形式保存,实现多位数的计算
s = 0; //初始化s,继续判断
}
else
{
printf("\t你输入的表达式有误!\n");
exit(0);
}
}
else
switch(Proceed(GetTop(&StackR),c[i])) //此函数用来比较读取的运算符和栈顶运算符的优先级
{
case '<': //栈顶的元素优先级低,当前运算符入栈
Push(&StackR,c[i]);
i++;
break;
case '=':
Pop(&StackR);
i++;
break;
case '>': //栈顶的优先级高则出栈,并将计算结果压入栈内
r = Pop(&StackR);
a = Pop(&StackD)-'0'; //操作数在栈内以ascii的形式存储,出站后要将ascii转化为整型,然后进行运算
b = Pop(&StackD)-'0';
Push(&StackD,Operate(a,r,b)) ;
break;
}
}
return (GetTop(&StackD)-'0'); // 将栈顶元素转化为整型的形式输出
}
int In(char c) //判断C是否为运算符是返回1否则返回0
{
char ch[7]={'+','-','*','/','#','(',')'};
int i;
for(i = 0; i < 7; i++)
if(c == ch[i])
return 1;
return 0;
}
char Proceed(char op,char c) //op为栈顶元素,c为当前读入的运算符,比较二者的优先级
{
char ch;
if(op=='(' && c==')' || op=='#' && c=='#' )
ch = '=';
else if(op=='+' || op=='-') /*栈顶元素为‘+’或‘-’的时候*/
switch(c)
{
case '+':
case '-':
case ')':
case '#': ch = '>'; break;
case '*':
case '/':
case '(': ch = '<';
}
else if(op=='*' || op=='/') /*栈顶元素为‘*’或‘/’的时候*/
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case ')':
case '#': ch = '>'; break;
case '(': ch = '<';
}
else if(op=='(') /*栈顶元素为‘(’的时候*/
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(': ch = '<'; break;
case '#':
printf("\tError!没有右括号!\n");
exit(0);
}
else if(op==')') //栈顶元素为‘)’的时候
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '#': ch = '>'; break;
case '(':
printf("\tError!括号匹配错误!\n");
exit(0);
}
else if(op=='#') //栈顶元素为‘#’的时候
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(': ch = '<'; break;
case ')':
printf("\tError!没有左括号!\n");
exit(0);
}
return ch;
}
int Operate(int a,char a1,int b)
{
int s;
int d1 = a;
int d2 = b; //把字符ab变为对应数字
switch(a1)
{
case '+':
s = d1+d2;
break;
case '-':
s = d2-d1;
break;
case '*':
s = d1*d2;
break;
case '/':
if(d1!=0)
{
s = d2/d1;}
else
{printf("\t除数不可以为0!\n");
exit(0);}
}
return (s+'0'); //将运算结果转化为ascii码的形式入栈,
}
本文档为【算数表达式的求解课程设计报告】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。