数据结构与算法课程设计--模拟简单计算器.docx

…………………………………………………………………………装…………………………………………………..…………………………..订………………………………………………………………..………线…………………………………………………………….

通达学院算法与数据结构设计报告
（ 2014/2015学年 第 二 学期 ）

题 目： 模拟简单计算器

目录
一、课题内容和要求 1
二、需求分析 1
三、概要设计 1
1设计理念 1
2.子函数功能 2
3.函数的调用 4
四、详细设计 4
五、测试及结果分析 11
加法测试 11
减法测试 11
乘法测试 12
除法测试 12
混合运算 13
六、调试过程中的问题 13
七、课程设计总结 15

一、课题内容和要求
利用所学的数据结构的基本知识，设计一个计算器（90）
输入：带有括号、+，-，X,/ 的表达式；
输出：运算结果
实例：输入：（4*3-（2+1））*2
输出： 18
要求：
1）对不合法输入进行检测并提示；
2）对合法输入求出正确解；
二、需求分析
本程序主要是采用栈的理论知识，主要用到两个结构体栈，一个用来转化表达式，一个用来计算表达式。
三、概要设计
1设计理念
首先，用一个字符数组来存储用户输入的中缀表达式。然后用栈来把这个表达式转化为后缀表达式，转化时要进行符号优先级比较，这里将‘*’‘/’的优先级定为2，‘+’‘-’定为1，括号和‘=’定为0。具体思想如下：例如用户输入了1+2*3=，将其存放入一个字符数组中。先在栈的底部存放一个‘=’号符，用作符号优先级比较。首先将1存放到另外一个字符数组s1中，再将‘+’号入栈。入栈的同时与底部的‘=’比较优先级，‘+’的优先级高于‘=’，所以不出栈，之后将2存放入s2中，然后再将‘*’入栈，入栈的同时与‘+’比较符号优先级，‘*’比‘+’高，所以不出栈。再将3存入s2中。之后将栈中不是‘=’的运算符都弹出栈，并依次存入s2中。所以s2中的表达式为123*+。之后进行计算，计算时用到浮点栈。首先将s2中的字符依次入栈，遇到运算符时进行计算。所以将123入栈后，再将‘*’入栈的同时，将前面两个数字进行运算，算出结果为6并存入栈中，之后再将‘+’入栈，再与1进行运算，结果即为7，然后输出结果。
2.子函数功能
pseqstack1 init_seqstack1(void)
{
pseqstack1 S;
S=(pseqstack1)malloc(sizeof(pseqstack1));
if(S)
S->top1=-1;
return S;
}初始化栈

int empty_seqstack1(pseqstack1 S)
{
if(S->top1==-1)
return 1;
else
return 0;
}
判断栈是否为空

int push_seqstack1(pseqstack1 S,datatype1 X
进栈

int pop_seqstack1(pseqstack1 S,datatype1 *X)
出栈

int GetTop(seqstack *s)
取栈顶元素

int PP(char op,char c)
比较栈顶元素与当前读入的运算符的优先级

int Ope(int a,char m,int b)
从数字栈中取出的两个数的计算

int priority(char op)
优先级判断函数

int infix_exp_value(char *infixexp,char *postfixexp
将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式

double postfix_exp(char *A)
求后缀表达式的值

3.函数的调用
主函数
栈的建立
typedef struct stack1 stack2
计算表达式
operand=operand*10+(ch-'0');
输出
postfix_exp(B)

四、详细设计

15

# include <stdio.h>
# include <malloc.h>
# include <conio.h>

# 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*/
pop_seqstack1(S,&a); /*运算符ch前的操作数出栈存入a*/
switch(ch) /*求 a ch b==? ,将结果赋给 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*/
return result;
}

/*优先级判断函数*/
int priority(char op)
{
switch(op)
{
case '#': return 1;
case ')': return 2;
case '+':
case '-': return 3;
case '*':
case '/': return 4;
case '(': return 5;
default : return 0;
}
}

/*将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式*/
int infix_exp_value(char *infixexp,char *postfixexp)
{
pseqstack2 S; /*定义栈S*/
int count=0;
char w; /*存放读取到的表达式(infixexp)的字符*/
char c; /*存放栈顶元素*/
char topelement;/*存出栈元素*/
S=init_seqstack2(); /*初始化栈*/
if(!S) /*栈的初始化判断*/
{
printf("栈初始化失败!");
return 0;
}
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) ) < priority(w) )
{/*如果栈顶为'('或者栈顶优先级小于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'*/
return 1;
}

/*主函数*/
int main()
{
int i=0;
char A[maxsize];
char B[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));
return 0;
getch();
}

五、测试及结果分析
加法测试
1+2+3=6

减法测试
5-2-1=2

乘法测试
1*2*3=6

除法测试
9/3/2=1.5

混合运算
1*（3+2）

六、调试过程中的问题
函数double postfix_exp(char *A)修改前后对比

函数int infix_exp_value(char *infixexp,char *postfixexp)修改前后对比

七、课程设计总结
通过这一周的课程设计，模拟简单计算器算法有了初步的了解。这次实验虽然时间不长，但是，我还是收获了许多，首先，要完成一个课程设计师需要我们有严谨的科学态度和扎实的理论知识作为基础和后盾的；其次，还要将理论知识与实际课题相结合，融会贯通。虽然我们之前对数据结构和C语言的联合使用并不熟悉，但通过老师的详细讲解和指导、及同学的互相帮助，最终完成了本次课程设计。在这次课程设计中，我们还存在着有待改进和完善的地方，还需要我们更加深入的去学习和了解这方面的知识，用更加完善的知识储备和自己的思考能力相结合，相信能够将此次课程设计做的更好，也能更好的提高自己的综合素质和能力！