数据结构课程设计报告简单计算器

1、计算机科学与信息工程学院数据结构课程设计设计题目：简单计算器 专 业计算机软件班 级 计软2班小组成员 蔡松佐 陈吉院 王希 刘军 符锦柏 曾祖滨 刘一霖指导教师张显全2010 年 12 月 25 日数据结构分工情况组长：蔡松佐组员：曾祖滨、陈吉院、符锦柏、刘军、刘一霖、王希王希：负责设计程序的整体框架（定义数据结构，编写主函数）评分：90分符锦柏：负责编写栈的代码评分：95分蔡松佐：负责编写计算算术表达式的代码评分：95分陈吉院：负责编写比较符号优先级的代码评分：90分曾祖滨：负责将所有代码整合成一个完整的程序评分：88分刘军：负责写实验报告评分：90分刘一霖：负责测试程序，看其是否具有良好

2、的健壮性评分：88分简单计算器一 基本功能描述简单的计算器的功能是对基本的加、减、乘、除、四则运算，可对输入的操作数，包括整数，小数等进行运算。二 设计思路本程序主要是采用栈的理论知识，主要用到两个结构体栈，一个用来转化表达式，一个用来计算表达式。区别就在于一个存储字符，一个存储浮点。首先，用一个字符数组来存储用户输入的中缀表达式。然后用栈来把这个表达式转化为后缀表达式，转化时要进行符号优先级比较，这里将*/的优先级定为2，+-定为1，括号和=定为0。具体思想如下：例如用户输入了1+2*3=，将其存放入一个字符数组中。先在栈的底部存放一个=号符，用作符号优先级比较。首先将1存放到另外一个字符数

3、组s1中，再将+号入栈。入栈的同时与底部的=比较优先级，+的优先级高于=，所以不出栈，之后将2存放入s2中，然后再将*入栈，入栈的同时与+比较符号优先级，*比+高，所以不出栈。再将3存入s2中。之后将栈中不是=的运算符都弹出栈，并依次存入s2中。所以s2中的表达式为123*+。之后进行计算，计算时用到浮点栈。首先将s2中的字符依次入栈，遇到运算符时进行计算。所以将123入栈后，再将*入栈的同时，将前面两个数字进行运算，算出结果为6并存入栈中，之后再将+入栈，再与1进行运算，结果即为7，然后输出结果。三 概要设计1，子函数功能struct Stack用来转化表达式的机构体栈。Struct FSt

4、ack用来计算表达式的结构体栈void InitStack(Stack &s)初始化结构体栈void InitFStack(FStack &s)初始化结构体栈char GetTop(Stack s)获取栈顶数据void IncrementStackSize(Stack &s)为栈扩充ncrementsize个存储空间void IncrementFStackSize(FStack &s)为栈扩充ncrementsize个存储空间void Push(Stack &s,char e)第一个栈入栈操作void PushF(FStack &s,float

5、e)第二个栈入栈操作bool Empty(Stack s)判断第一个栈是否为空。bool EmptyF(FStack s)判断第二个栈是否空char Pop(Stack &s)表达式出栈float PopF(FStack &s)计算的数据出栈int Precede(char op)确定优先级的函数void Change(char *s1,char *s2)改变两个字符串的储存位置float Compute(char *s2)实现数据的运算2 函数的调用主函数栈的建立Stack，FStackChange(str1,str2)计算表达式Compute(str2)InitFStack

6、(S);PushF(S,x)PopF(S)输出cin.getline(str1,2);3 测试数据及测试结果(1)测试 1+2+3=6(2) 测试2*4=8(3)测试 3/2=1.5(4)测试(1+2)*3=9四 程序代码#include <iostream.h>#include <fstream.h>#include <string.h>#include <ctype.h>#include <stdlib.h>#include <strstrea.h>struct Stack /转换表达式char *elem;int t

7、op;int stacksize;int incrementsize;struct FStack /计算float *elem;int top;int stacksize;int incrementsize;void InitStack(Stack &s)s.elem=new char100;s.top=-1;s.stacksize=100;s.incrementsize=10;void InitFStack(FStack &s)s.elem=new float100;s.top=-1;s.stacksize=100;s.incrementsize=10;char GetTop

8、(Stack s)return s.elems.top;void IncrementStackSize(Stack &s)char *a=new chars.stacksize+s.incrementsize;for(int i=0;i<=s.top;i+)ai=s.elemi;delete s.elem;s.elem=a;s.stacksize+=s.incrementsize;void IncrementFStackSize(FStack &s)float *a=new floats.stacksize+s.incrementsize;for(int i=0;i<

9、;=s.top;i+)ai=s.elemi;delete s.elem;s.elem=a;s.stacksize+=s.incrementsize;void Push(Stack &s,char e)if(s.top=(s.stacksize-1)IncrementStackSize(s);s.top+;s.elems.top=e;void PushF(FStack &s,float e)if(s.top=(s.stacksize-1)IncrementFStackSize(s);s.top+;s.elems.top=e;bool Empty(Stack s)return s.

10、top=-1;bool EmptyF(FStack s)return s.top=-1;char Pop(Stack &s) /表达式出栈return s.elems.top-;float PopF(FStack &s) /计算的数据出栈return s.elems.top-;int Precede(char op) /确定优先级的函数switch (op)case '+':case '-':return 1; /定义加减运算的优先级为1case '*':case '/':return 2; /定义乘除运算的优先级

11、为2case '(':case '':case '':case '=':default:return 0; /定义在栈中的左括号和栈底字符的优先级为0void Change(char *s1,char *s2)Stack R; /定义用于暂存运算符的栈InitStack(R);Push(R,'='); /给栈底放入='字符，它具有最低优先级0int i,j;i = 0; /用于指示扫描s1串中字符的位置，初值为0j = 0; /用于指示s2串中待存字符的位置，初值为0char ch = s1i;while

12、(ch != '=')if (ch = ' ')ch = s1+i; /对于空格字符不做任何处理/-else if (ch = '(') /对于左括号，直接进栈Push(R,ch);ch = s1+i;else if (ch = ')') /对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入到s2中while (GetTop(R) != '(')s2j+ = Pop(R);Pop(R); /删除栈顶的左括号ch = s1+i; /-else if (ch = '') /对于左括号，直接进栈Pu

13、sh(R,ch);ch = s1+i;else if (ch = '') /对于右括号，使括号内的仍停留在栈中的运算符依次 /出栈并写入到s2中while (GetTop(R) != '')s2j+ = Pop(R);Pop(R); /删除栈顶的左括号ch = s1+i; /-else if (ch = '') /对于左括号，直接进栈Push(R,ch);ch = s1+i;else if (ch = '') /对于右括号，使括号内的仍停留在栈中的运算符依次 /出栈并写入到s2中while (GetTop(R) != '&

14、#39;)s2j+ = Pop(R);Pop(R); /删除栈顶的左括号ch = s1+i; /-else if (ch = '+' | ch = '-' | ch = '*' | ch = '/') /对于四则运算符，使暂存在栈中的不低于ch优先级 /的运算符依次出栈并写入到s2中char w = GetTop(R);while (Precede(w) > Precede(ch) /优先级()函数返回运算符形参的优先级s2j+ = w;Pop(R);w = GetTop(R);Push(R,ch);ch = s1+i;el

15、se /此处为数字或小数点字符的处理while (isdigit(ch) | ch = '.')s2j+ = ch;ch = s1+i;s2j+ = ' ' /被转换后的每个数值后放一个空格/-ch = Pop(R);while (ch != '=')s2j+ = ch;ch = Pop(R);s2j+ = '=' /加入字符串结束符s2j+ = '0'float Compute(char *s2)FStack S; /用S栈存储操作数和中间计算结果InitFStack(S);istrstream ins(s2);

16、 /把s2定义为输入字符串流对象inschar ch; /用于输入字符float x; /用于输入浮点数ins>>ch;while (ch != '=')switch (ch)case '+':x = PopF(S) + PopF(S);break;case '-':x = PopF(S);x = PopF(S) - x;break;case '*':x = PopF(S) * PopF(S);break;case '/':x = PopF(S);x = PopF(S) / x;break;defaul

17、t:ins.putback(ch);ins>>x;PushF(S,x);ins>>ch;if (!EmptyF(S)x = PopF(S);if (EmptyF(S) /如果栈中只有一个值那一定是结果return x;void main()/主程序FStack s;char a10;float b,c;char str150,str250; /暂时存储表达式char j='y'cout<<" *欢迎使用本计算器*"<<endl<<endl;haha:while(j='Y'|j=

18、9;y')int i=0,m=0,n=0,k=0,l=0,q=0,p=0;cout<<" 请输入一个以'='字符结束的中缀算术表达式："<<endl<<endl;cin.getline(str1,sizeof(str1);while(str1i!='0')i+;if(str1i-1!='=')cout<<"表达式错误.请重新输入."<<endl<<endl;goto haha;i=0;while(str1i!='0

19、9;)if(str1i='0'&&str1i-1='/')cout<<"表达式错误.请重新输入."<<endl<<endl;goto haha;i+;i=0;while(str1i!='0')if(str1i='(')m+;if(str1i=')')n+;if(str1i='')k+;if(str1i='')l+;if(str1i='')q+;if(str1i='')p+;i+;if(m!=n | k!=l | q!=p)cout<<"表达式错误.请重新输入."<