软件技术基础实验报告实验名称：表达式计算器系别：通信工程年级：班级：学生学号：学生姓名：《数据结构》课程设计报告题目简易计算表达式的演示【题目要求】要求：实现基本表达式计算的功能输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值基本操作：键入表达式，开始计算，计算过程和结果记录在文档中难点：括号的处理、乘除的优先级高于加减1．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。
因而在程序设计时，借助栈实现。
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。
为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。
算法输出：表达式运算结果。
算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。
在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
2．概要设计2.1 数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符。
栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。
2.2 算法设计为了实现算符优先算法。
可以使用两个工作栈。
一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。
2.3 ADT 描述 ADT Stack{ 数据对象：D={ia |i a∈ElemSet,i=1,2,…，n, n ≧0}数据对象：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定n a端为栈顶，i a端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈S。
GetTop(S)初始条件：栈S已存在。
操作结果：用P返回S的栈顶元素。
Push(&S，ch)初始条件：栈S已存在。
操作结果：插入元素ch为新的栈顶元素。
Pop(&S)初始条件：栈S已存在。
操作结果：删除S的栈顶元素。
In(ch)操作结果：判断字符是否是运算符，运算符即返回1。
Precede(c1, c2)初始条件：c1,c2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
Operate(a,op,b)初始条件：a,b为整数，op为运算符。
操作结果：a与b进行运算，op为运算符，返回其值。
num(n)操作结果：返回操作数的长度。
EvalExpr()初始条件：输入表达式合法。
操作结果：返回表达式的最终结果。
}ADT Stack2.4 功能模块分析1.栈的基本功能。
InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack *s,char ch) 运算符栈插入ch为新的栈顶元素，Push2(Stack2 *s,int ch) 操作数栈插入ch为新的栈顶元素，Pop(Stack *s) 删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2 *s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stack s)用p返回运算符栈s的栈顶元素，GetTop2(Stack2 s) 用p返回操作数栈s的栈顶元素。
2.其它功能分析。
(1)In(char ch) 判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。
(2) Precede(char c1,char c2) 判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。
(3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。
运算结果直接返回。
(4) num(int n) 求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。
(5) EvalExpr()主要操作函数运算功能。
分析详细见“3.详细设计…3.2”。
3．详细设计3.1 数据存储结构设计因为表达式是由操作符，运算符和界限符组成的。
如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。
/* 定义字符类型栈*/struct stacklifei1 //数字栈的定义{double *base;double *top;}s1;/struct stacklifei2 //运算符栈的定义{char *base;char *top;}s2;3.2 计算功能的实现void jisuan() // 该函数对数字栈的前两个栈顶//元素与符号栈的栈顶元素完成一次运算操作{double a,b;b=*(s1.top-1);s1.top--;if(s1.top==s1.base){error=1;return ;}a=*(s1.top-1);switch(*(s2.top-1)){case '+':a=a+b;break;case '-':a=a-b;break;case '*':a=a*b;break;case '/':if(b==0){error=2;s2.top=s2.base;return ;}//除数不为0else a=a/b;break;default :error=1;}fprintf(file,"%lf %c %lf= %lf\n",*(s1.top-1),*(s2.top-1),b,a);*(s1.top-1)=a; //将运算结果入栈s2.top--;return ;}3.3函数表达式求值功能的实现void qiuzhi(char *cr)该函数完成对表达式的处理{int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2.base=s2.top=fuha;*(s2.top)='#';s2.top++;while(s2.top!=s2.base){sum=0;flag=0;k=10;j=1;h=1;while(cr[i]>='0'&&cr[i]<='9'||cr[i]=='.')//若当前的字符是数字，就将char型的数据转换为double型{if(cr[i]=='.'){if(cr[i-1]<'0'||cr[i-1]>'9'||i==0||cr[i+1]<'0'||cr[i+1]>'9'){error=1;break;}else{k=1;h=10;}}else{flag=1;j=j*h;sum=sum*k+(cr[i]-48)/j;}i++;}3.4对函数表达式每个字符的操作switch(cr[i]){case '-':if(cr[i-1]=='('||i==0){fuhao=1;i++;break;}//判断是不是负号，若不是则进行与加号相同的操作//当'-'出现在表达式第一位或是'('后第一位,则应将其判为负号case '+'://加、减号的优先级只比'('和'='高，若栈顶元素为这两者之一//就将其入栈，否则执行运算操作if(*(s2.top-1)=='('||*(s2.top-1)=='#'){*(s2.top)=cr[i];s2.top++;i++;}else jisuan();break;case '*':case '/'://乘、除号的优先级只比'*'、'/'和'^'低，若栈顶元素为这三者之一//就执行运算操作，否则将其入栈if(*(s2.top-1)=='*'||*(s2.top-1)=='/')jisuan();else{*(s2.top)=cr[i];s2.top++;i++;}break;case '(': *(s2.top)=cr[i]; s2.top++;i++;break;//未入栈时'('的优先级最高，所以它一定要入栈//但一入栈其优先级就应降为最低case ')'://注意：由于'()'运算优先级最高故我直接进行运算，//直到栈顶元素为'('后将'('出栈，故符号栈中一定没有')'，//这也是我进行以上优先级判断的前提if(*(s2.top-1)=='('){s2.top--;i++;}else jisuan();break;case '='://表达式结束，若符号栈栈顶元素不为'#'，进行运算//否则退栈，结束if(*(s2.top-1)=='#'){s2.top--;}else jisuan();break;default :i++; //清除空格及未定义符号}3.5主菜单页面的实现void main(){char cr[60];char c='a';file=fopen(outfile,"w+");//使用提示printf("****************************************************************** *************\n");printf("*********************************李斐计算器************************************\n");printf("四则简易计算器\n\n");printf("输入表达式例如2+4= \n\n");printf("最后按# 键则会退出保存\n\n");printf("谢谢使用\n\n");printf("------------------------------------------------------------------------------\n");printf("****************************************************************** ************\n");//循环输入表达式，按'#'键退出while(c!='#'){error=0;printf("输入表达式:\n");gets(cr);fprintf(file,"表达式：%s\n",cr);qiuzhi(cr);printf("任意键继续，按# 键退出:\n");c=getch();}fclose(file);}【附加一】算符间的优先关系如下：4．软件测试1.运行成功后界面。