B7合运算表达式的求值以及大整数计算
课程设计模板—表达式求值及大整数计算
《数据结构》课程设计报告
题目：实现对算术四则混合运算表达式的求值以及大整数计算
一．设计目的
数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
二．问题描述
(一)当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算
符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于
异常表达式能给出错误提示。
(二)求两个不超过200位的非负整数的和，积和商。
三．需求分析
本程序所做的工作为：能直接求出四则表达式的值，并输出；可以解决因数值位数太大unsigned类型都无法表示的大数之间的运算。本程序可用于小学教师对学生作业的快速批改以及对数值位数要求较大的科学运算。
此程序规定：
(一)程序的主要功能包括两部分：表达式求解和大整数的运算。
(二)表达式求解中输入的必需为一个正确的四则表达式，可以是整型也可以为浮点型，
比如：3*(7-2)+5和3.154*(12+18)-23。大整数的运算中根据提示要输入两行数据
位数不能大于200位。
(三)程序的输出：表达式求解中为一浮点型数据，大整数运算中输出的即为运算之后的
结果，结果里不能有多余的前导0。
四．概要设计
1.ADT LinkStack{
数据元素：此链栈中的所有元素类型为字符型的数字字符
数据关系：栈中数据元素之间是线性关系。
基本操作:
（1）InitStack(LinkStack &head)
操作结果：构造一个空栈head
（2）IsEmpty(LinkStack head)
初始条件：栈head已存在
操作结果：若栈为空栈，则返回TRUE,否则FALSE
（3）Push(LinkStack &head,ElementType element)
初始条件：栈head已存在
操作结果：插入元素element为新的栈顶元素
（4）Pop(LinkStack &head,ElementType &element)
初始条件：栈head已存在且非空
操作结果：删除head的栈顶元素，并用e返回其值
（5）GetTop(LinkStack head, ElementType &element)
初始条件：栈head已存在并且非空
操作结果：用e返回head的栈顶元素
（6）DestroyStack(LinkStack &head)
初始条件：栈head已存在
操作结果：栈head 被销毁
}ADT LinkStack
2．ADT LinkCharStack{
数据对象D：元素类型为字符型的符号字符
数据关系R：
基本操作：栈中数据元素之间是线性关系。
（1）CInitStack(LinkCharStack &head)
（2）CIsEmpty(LinkCharStack head)
（3）CPush(LinkCharStack &head,ElementType element)
（4）CPop(LinkCharStack &head,ElementType &element)
（5）CGetTop(LinkCharStack head, ElementType &element)
（6）CDestroyStack(LinkCharStack &head)
}ADT LinkCharStack
●系统中子程序及功能要求：
（1）add():计算两个不大于200位的大整数的和，此文件包含于头文件calculator.h中。
（2）multiply()：实现两个大整数的积的运算，此文件也包含于头证件calculator.h中。
（3）Comop(char ch)：判断输入的字符是否为运算符
（4）char Precede(char ch,char c)：比较两个运算符的优先级，ch是栈顶字符，c是表达式字符。
（5）ElementType Operate(ElementType a,char ch,ElementType b)：解析表达式中的双目运算，其返回的结果即为双目运算表达式的值。
（6）int error(char *str) ：错误提示函数，实现对多种非法四则表达式的判断，并给出提示，让用户更正自己的输入错误。
（7）void MenuPrint()：主菜单打印函数。
（8）void submenu()：大整数运算功能模块的子菜单。
（9）void Clear()：清屏函数。
（10）ElementType EvaluateExpression(char *exp)：这是此程序的核心函数，可以综合其它子函数，实现最终的表达式求解。
●各程序模块之间的调用关系（子程序编号见上）：
主函数可调用子程序1，2，7，8，9，10。
子程序10可调用子程序3，4，5，6。
五．详细设计
?表达式计算核心算法的思想及伪代码：
此算法的基本思想：
首先置操作数栈OPND为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）
此算法的伪代码：
ElementType EvaluateExpression(char *exp){
定义两个字符变量c和ch,c代表输入表达式中的字符，ch代表栈顶运算符;
定义字符指针 *p,*q,*temp;temp指向运算符后面的一个字符
double i=0,a=0,b=0;
将传入的实参赋给p,q;
定义一个运算符栈 OPTR;
定义一个操作数栈 OPND;
调用函数InitStack()初始化栈OPND;
调用函数InitCharStack()初始化栈OPNR ;
调用函数CPush(OPTR,'#')将#压入运算符栈;
c=*p;temp=p;p++;
if(第一个字符就为‘-’)
{
c=*p;temp=p;p++;
}
while(栈不为空或表达式没有结束)
{//进入最外层循环
if(不是运算符)//则解析数字字符串然后进操作数栈
{
整数部分m=0;
小数部分n=0;
while(没有遇到小数点并且为数字字符)
{ 解析整数部分m }
if(遇到小数点)
{ 解析小数部分
c=*p;
将p指针移到第一个出现的字符;
将q指针指向小数的最后一位;
while(p指针不指向’.’)
{
将p指向的字符转为小数n
p--;
}
p=q;
p++;
}
if(运算符为‘-’并且运算符前一个为‘（’或者为表达式的开始) 调用Push(OPND,-(m+n))将m+n的相反数入栈;
else
调用Push(OPND,m+n)将m+n入栈;
}数字进栈结束
else//是运算符时则进栈OPTR
{
if(运算符为‘-’&&运算符前一个为‘（’)
{
c=*p;
temp=p;
p++;
}
else
{
调用函数CGetTop(OPTR,ch)得到OPTR的栈顶元素;
switch(调用函数Precede(ch,c)判断栈顶元素与接收的字符的优生级别) {
case 栈顶运算符优先权低:
调用函数CPush(OPTR,c)将c入运算符栈;
接收下一个字符;
case 栈顶运算符优先权高：
运算符出栈得到ch;
数字栈连续出栈两次得到a,b ;
调用Operate(a,ch,b)并将结果入栈到数字栈;break;
case 优生权相等：脱括号并接收下一个字符;
调用CPop(OPTR,ch)脱括号;
接收下一个字符;
default:
接收下一个字符;
}退出switch循环
}//else1
}//else2
}//退出最外层while循环
调用函数GetTop(OPND,i)得到栈顶元素i;
将两个栈消毁;
返回I;
}EvaluateExpression函数结束
?实现大整数相加的add()函数的伪代码：
void add()
{
输入两个要运算的大整数分别存在长度为MAX_LEN+10的
字符串数组szline1和szline2中;
循环计数变量 i,j;
调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;
调用库函数memeset()将地址an2开始的sizeof(an2)字节内容置成0;
将szline1中存储的字符串形式的整数转换到an1中去
将szline1中存储的字符串形式的整数转换到an1中去
for(i=0;i<最大的长度;i++)
{
an1[i]+=an2[i];
如果(得到结果大于10)
{
原位an1[i]-=10;
高位an1[i+1]++即进位;
}
}
//下面是无前导0地输出计算的结果;
for(i=最大长度;i>=0;i--)
{
如果没有标记第一次出现过了0
那么输出an1[i];
否则如果 an1[i]为0
则输出an1[i];
标记已经出现过0;
}
}
?实现大整数相加的add()函数的伪代码：
void multiply()
{
输入两个要运算的大整数分别存在长度为MAX_LEN+10的
字符串数组szline1和szline2中;
循环计数变量 i,j;
调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;
调用库函数memeset()将地址an2开始的sizeof(an2)字节内容置成0;
调用库函数memeset()将地址aresult开始的sizeof(aresult)字节内容置
成0。
将szline1中存储的字符串形式的整数转换到an1中去
将szline1中存储的字符串形式的整数转换到an1中去
for(i=0;i //从an1的个位开始 for(j=0;j aresult[i+j]+=an2[i]*an1[j];两数第i,j位相乘，累加到结果的第i+j位 } 下面的循环统一处理进位问题 for(i=0;i { if(aresult[i]>=10){ aresult[i+1]+=aresult[i]/10; aresult[i]%=10; } } 输出结果和上一函数一样 } 六．测试分析 按照附录中的测试数据，得出如下测试、分析结果： （1）表达式求解功能 当我们输入表格中两个正确的四则表达式时程序能准确地求得其值： 完全支持浮点数，正负数的运算; 而当我们输入第三组错误的表达式时，程序能做出正确判断，提醒用给用户输入一个正确的表达式。 其数据测试的情况见截图： 表达式一运算结果由表一知结果正确。 表达式二运算结果由表一知结果正确。 表达式三运算出错情况 （2）大整数加法功能 输入两组不大于200位的大整数，能准确计算出结果其截图如下图所示： 选择功能b （3）大整数乘法功能 其测试截图如： 第二组数据 结果正确。 分析结果：由以上各组数据的测试可以看出，本程序达到了其需求的功能。 存在的不足：大整数运算输出的结果比较混乱，应该适合地应用空格和换行，使输出的结果 清楚明朗。 七．使用说明 1．运行程序，首先出现主菜单。主菜单包括四个选项：选项a：表达式求解，选择该项可进行四则表达式的求解；选项b：大整数运算，选择该项可进行不大于200位的大整数的加法和乘法运算（目前只支持加，乘）；选项c：清屏；选项d：退出程序，选择该项将退出程序。 2．大整数运算界面包括4个选项：选项1：两个大整数相加；选项2：两个大整数相乘；选项3：返回上一级菜单，可返回主界面。选项4：直接退出本程序。 八．附录（一）：测试数据 （表一） （表二） 九．附录（二）：C语言实现（源代码） 源程序文件名清单： LinkStack.h//链栈的实现数字栈 LinkCharStack.h//链栈的实现符号栈 Calculator.h//主要实现大整数的加，乘运算 Calculator.cpp//主程序 LinkStack.h头文件 //这个栈是用来存储数字符的 #include #define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 typedef double ElementType; typedef int Status; typedef struct node{ ElementType data; struct node *next; }StackNode, *LinkStack; void InitStack(LinkStack &head){ head=(LinkStack)malloc(sizeof(StackNode)); head->next=NULL; } Status IsEmpty(LinkStack head){ if(head->next==NULL)return TRUE; else return ERROR; } Status Push(LinkStack &head,ElementType element){//入栈LinkStack p; p=(LinkStack)malloc(sizeof(StackNode)); if(p== NULL) return FALSE; p->data=element; p->next=head->next; head->next=p; return OK; } Status Pop(LinkStack &head,ElementType &element){//出栈if(IsEmpty(head))return FALSE; LinkStack temp=head->next; element=temp->data; head->next=temp->next; free(temp); return OK; } int GetTop(LinkStack head, ElementType &element){ if(head->next==NULL) return ERROR; element =head->next->data; return OK; } Status DestroyStack(LinkStack &head) { LinkStack q; while(head) { q=head->next; free(head); head=q; } return TRUE; } LinkStack_Char.h头文件 //这个栈是用来存储符号字符的 #include #define TRUE 1 #define FALSE 0 #define NULL 0 typedef char ElemType; typedef int Status; typedef struct node1{ ElemType data; struct node1 *next; }StackCharNode,*LinkCharStack; void CInitCharStack(LinkCharStack &head){ head=(LinkCharStack)malloc(sizeof(StackCharNode)); head->next=NULL; } int CIsEmpty(LinkCharStack head){ return (head->next==NULL)?TRUE:FALSE; } int CPush(LinkCharStack &head,ElemType element){ LinkCharStack temp=(LinkCharStack)malloc(sizeof(StackCharNode)); if(!temp)return ERROR; temp->data=element; temp->next=head->next; head->next=temp; return TRUE; } int CPop(LinkCharStack &head,ElemType &element){ if(CIsEmpty(head))return FALSE; StackCharNode *temp=head->next; element=temp->data; head->next=temp->next; free(temp); return TRUE; } int CGetTop(LinkCharStack head,ElemType &element){ if(head->next!=NULL) { element=head->next->data; return TRUE; } element='#'; return FALSE; } Status CDestroyStack(LinkCharStack &head){ LinkCharStack q; while(head) { q=head->next; free(head); head=q; } return TRUE; } calculator.h头文件 /*calculator.h头文件*/ #include #include #define MAX_LEN 200 unsigned int an1[MAX_LEN+10]; unsigned int an2[MAX_LEN+10]; unsigned int aresult[MAX_LEN*2+10]; char szline1[MAX_LEN+10]; char szline2[MAX_LEN+10]; void add() { printf("请输入两个要运算的大整数:\n"); scanf("%s",szline1); scanf("%s",szline2); int i,j; memset(an1,0,sizeof(an1));//库函数memeset将地址an1开始的sizeof(an1)字节内容置成 memset(an2,0,sizeof(an2)); //下面将szline1中存储的字符串形式的整数转换到an1中去 //an1[0]对应于个位 int nlen1=strlen(szline1); j=0; for(i=nlen1-1;i>=0;i--) an1[j++]=szline1[i]-'0'; int nlen2=strlen(szline2); j=0; for(i=nlen2-1;i>=0;i--) an2[j++]=szline2[i]-'0'; for(i=0;i { an1[i]+=an2[i]; if(an1[i]>=10)//看是否要进位 { an1[i]-=10; an1[i+1]++;//进位 } } printf("计算的结果为：\n"); bool bstartoutput=false; for(i=MAX_LEN;i>=0;i--) if(bstartoutput) printf("%d",an1[i]); else if(an1[i]){ printf("%d",an1[i]); bstartoutput=true; } } void multiply() { printf("请输入两个要运算的大整数:\n"); scanf("%s",szline1); scanf("%s",szline2); int i,j; memset(an1,0,sizeof(an1));//库函数memeset将地址an1开始的sizeof(an1)字节内容置成 memset(an2,0,sizeof(an2)); memset(aresult,0,sizeof(aresult)); //下面将szline1中存储的字符串形式的整数转换到an1中去 //an1[0]对应于个位 int nlen1=strlen(szline1); j=0; for(i=nlen1-1;i>=0;i--) an1[j++]=szline1[i]-'0'; int nlen2=strlen(szline2); j=0; for(i=nlen2-1;i>=0;i--) an2[j++]=szline2[i]-'0'; //以下为进行计算 for(i=0;i //从an1的个位开始 for(j=0;j aresult[i+j]+=an2[i]*an1[j];//两数第i,j位相乘，累加到结果的第i+j 位 } //下面的循环统一处理进位问题 for(i=0;i { if(aresult[i]>=10){ aresult[i+1]+=aresult[i]/10; aresult[i]%=10; } } printf("计算的结果为：\n"); bool bstartoutput=false; for(i=MAX_LEN*2;i>=0;i--){ if(bstartoutput) printf("%d",aresult[i]); else if(aresult[i]){ printf("%d",aresult[i]); bstartoutput=true; } } } Calculator.cpp # include # include # include # include"LinkStack.h" # include"LinkCharStack.h" # include"calculator.h" # define STACK_INIT_SIZE 30 # define STACKINCREAMENT 10 # define NUMBER 30 //判断ch是否为运算符 int Comop(char ch) { switch(ch) { case'+': case'-': case'*': case'/': case'(': case')': case'#':return 1; default:return 0; } }//Comop //比较两个运算符的优先级 char Precede(char ch,char c)//ch是栈顶字符,c 是表达式字符 { switch(ch) { case'+': case'-': if(c=='+'||c=='-'||c==')'||c=='#')return'>'; if(c=='*'||c=='/'||c=='(')return'<'; case'*': case'/': if(c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c=='#')return'>'; if(c=='(')return'<'; case'(': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')return'<'; if(c==')')return'='; if(c=='#')return' '; case')': if(c=='+'||c=='-'||c=='*'||c=='/'||c==')')return'>'; if(c=='(')return' '; if(c=='#')return'>'; case'#': if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')return'<'; if(c==')')return' '; if(c=='#')return'='; default: return'$'; } }//precede //运算函数 ElementType Operate(ElementType a,char ch,ElementType b) { switch(ch) { case'+':return a+b; case'-':return a-b; case'*':return a*b; case'/': if(b==0) { return -32767; } return a/b; default: return -32767; } }//Operate //错误提示函数 int error(char *str) //在用的过程中可以不断扩充错误的类型 { int i=0,err=0; while(str[i]!='#') //主要通过判断所有输入的字符数组str[30] { if(err==1 //err是为有些字符并不满足其它函数而设的一个错误点 ||( (str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.') && //其它函数只要一声明err=1也就说明输入有误 (str[i+1]==')') ) ||( (str[i]=='+'||str[i]=='*'||str[i]=='/'||str[i]=='.') && (str[i-1]=='(') ) ||(str[i]==')' && str[i+1]=='.') ||(str[i]=='.' && str[i+1]=='(') ||(str[i]==')' && str[i+1]=='(') ||(str[i]=='(' && str[i+1]==')') ||(str[i]==')' && str[i+1]>='0'&&str[i+1]<='9') ||(str[i]>='0'&&str[i]<='9'&& str[i+1]=='(') ||(str[0]=='+'||str[0]=='*'||str[0]=='/'||str[0]==')') ||( (str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.') && (str[i+1]=='+'||str[i+1]=='-'||str[i+1]=='*'||str[i+1]=='/'||str[i+1]=='.') ) ||(int(str[i])>57) ||(str[i]=='/' && str[i+1]=='0') ||(int(str[i])>31 && int(str[i])<38) ) return 1; else if(str[i]=='#')return 0; i++; }//while return 0; }//错误提示函数 //表达式计算 ElementType EvaluateExpression(char *exp){ char c,ch; //c代表输入表达式中的字符，ch代表栈顶运算符 char *p,*q,*temp;//temp指向运算符后面的一个字符 double i=0,a=0,b=0; p=q=exp; LinkCharStack OPTR;//运算符栈 LinkStack OPND;//操作数栈 CInitCharStack(OPTR);CPush(OPTR,'#'); InitStack(OPND); c=*p;temp=p;p++; if(c=='-') { c=*p;temp=p;p++; } while(c!='#'||!CIsEmpty(OPTR)) //栈不为空或表达式没有结束 {//*********************进入最外层循环********************* if(!Comop(c))//不是运算符则解析数字字符串然后进操作数栈 { double m=0,n=0; while(c!='.'&&c>='0'&&c<='9') {//解析整数部分 m=m*10+(c-48); c=*p; p++; } if(c=='.') {//解析小数部分 c=*p; while(c>='0'&&c<='9') {p++;c=*p;} q=p; p--; while(*p!='.') { n=n/10+(*p-48)/10.0; p--; } p=q; p++; } if(*(temp-2)=='('&&*(temp-1)=='-'||temp-1==exp) Push(OPND,-(m+n)); else Push(OPND,m+n); }//*****数字进栈结束****** else//是运算符时则进栈OPTR { if(c=='-'&&*(p-2)=='(') { c=*p; temp=p; p++; } else//else1 { CGetTop(OPTR,ch); switch(Precede(ch,c)) { case'<'://栈顶运算符优先权低 CPush(OPTR,c);c=*p;temp=p;p++;break; case'>'://栈顶运算符优先权高 CPop(OPTR,ch); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,ch,b));break; case'='://脱括号并接收下一个字符 CPop(OPTR,ch);c=*p;temp=p;p++;break; default: c=*p;temp=p;p++; }//switch }//else1 }//else2 }//退出最外层循环 GetTop(OPND,i); DestroyStack(OPND); CDestroyStack(OPTR); return i; }//EvaluateExpression函数结束 //菜单函数 void MenuPrint() { printf("\t\t┌─────────┐\n"); printf("\t\t│多功能计算器│\n"); printf("\t\t├(a)表达式求解│\n"); printf("\t\t├(b)大整数运算│\n"); printf("\t\t├(c)清屏│\n"); printf("\t\t├(d)退出│\n"); printf("\t\t└─────────┘\n"); printf("\t\t请输入你要进行的操作:"); } //菜单函数 void submenu() { printf("\t\t┌─────────────┐\n"); printf("\t\t│（）两个大整数相加│\n"); printf("\t\t│（）两个大整数相乘│\n"); printf("\t\t│（）返回上级菜单│\n"); printf("\t\t│（）退出本程序│\n"); printf("\t\t└─────────────┘\n"); printf("\t\t请选择："); } //清屏函数 void Clear() { char a; printf("请按回车键继续……\n"); a=getchar(); a=getchar(); system("cls");