数据结构课程设计报告课设题目：算式表达式求值系统班级: 软件1202姓名：学号：****: **成绩:2013 年1月目录一、需求分析 (2)二、概要设计 (2)(一）设计思想 (2)(二）实现方法 (2)(三）模块整体设计图 (3)(四）函数功能介绍 (3)三、详细设计 (4)（一）数据结构设计 (4)（二）模块接口设计 (4)（三）盒图 (5)四、调试分析 (7)五、用户手册 (7)六、测试结果 (8)七、附录 (9)附录一设计体会 (9)附录二源程序 (9)一、需求分析算式表达式求值是程序设计语言编译中一个最基本的问题。
本次任务要求完成一个四则算式表达式求值系统。
具体需求为：当用户输入一个四则算式（包括加、减、乘、除和括号），如（12+3）*2+9*4，输出其计算结果。
具体要求如下：（一）要实现栈的基本操作算法，包括初始化栈、进栈、出栈等。
（二) 在本程序中，表达式中的元素限定为char型，表达式长度不超过100，表达式以“#”号为结束标志。
（三）要求程序输出表达式的计算结果。
二、概要设计（一）设计思想本次四则算式表达式求值的程序采用的是中缀表达式的求值的方法。
所谓中缀表达式，就是指每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+ 、- 、*、/、%、^（乘方）和括号（）。
而本次程序的编写只涉及四则运算（+、-、*、/）和括号（）。
设运算规则为：．运算符的优先级为：（）> *、/> +、- ；．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1和算符栈s2。
当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符“#”。
根据运算规则，左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低了; 乘方运算的结合性是自右向左，所以，它的栈外级别高于栈内; 就是说有的运算符栈内栈外的级别是不同的。
当遇到右括号“）”时，一直需要对运算符栈出栈，并且做相应的运算，直到遇到栈顶为左括号“(”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。
对象栈初始化为空。
根据以上分析，每个运算符栈内、栈外的级别如下：算符栈内级别栈外级别^ 3 4*、/、% 2 2+、- 1 1( 0 4） -1 -1（二）实现方法由于算符是字符类型，而表达式中的数字为数值类型，如果建立两个栈的结构的话，他们除了数据元素不同，其余操作都是类似的，这样不仅会增加程序的空间开销和执行时间，而且也使程序冗余度较大。
我采用的解决方案是设置一个算符值x来表示算符，+、-、*、/、（、）的算符值依次为：1,2,3,4,5,6，用一个switch-case语句将算符转化为相应的数值，然后再入栈，这样就统一了对象栈和算符栈元素的数据类型。
在将“（”出栈时，要避免将初值0数据多次入栈而导致出错，如2*（3-1）-1，正常情况下在遇到*时，就应该将数字2入对象栈，然后将保存算式中数值的变量a置零，但是当遇到“（”时，又要将数字0入栈，这样就会导致结果出错，所以在用户输入的数据入对象栈之前，应先判断是否为“（”，若为“(”,则不能将数据入对象栈；当遇到“）”时，“（”不能入栈，并且要将前面的“3”，“-”，“1”都依次出栈进行计算，在遇到“（”时，将“（”出栈，但接下来又会遇到“-”，因此又要将数字0入栈，这样也会导致结果出错因此，我用了一个z[Max]数组来存放“（”的算符值，在每次入对象栈之前，都需要判断在z[i-1]的值。
在解决了数据类型问题之后，程序的编写就显得容易多了。
基本的操作包括栈的初始化、入栈、出栈、判空栈以及取栈顶元素，然后按照设计思路编写求四则表达式值的程序，此外还有一个界面程序，通过调用清屏函数system("cls")以及switch-case语句来实现界面的切换。
（三）模块整体设计图（四）函数功能介绍1.主函数void main()功能：调用其他各个函数；2.菜单函数 int menu()功能：构造系统界面；3.算式求值函数void suanshi()功能：求解四则算式表达式之值4.栈初始化函数SeqStack *Init_SeqStack()功能：置空栈5.入栈函数int Push_SeqStack (SeqStack *s, int x)功能：将数据元素入栈6.出栈函数int Pop_SeqStack(SeqStack *s, int *x)功能：将数据元素出栈7.取栈顶元素函数int Top_SeqStack(SeqStack *s)功能：取出栈顶元素并将栈顶指针减一8.判空栈函数int Empty_SeqStack(SeqStack *s)功能：判断是否为空栈三、详细设计（一）数据结构设计1.本系统采用结构体来定义栈，其结构如下:typedef struct{int data[Max];int top;}SeqStack;并且设置了两个栈s1,s2分别表示对象栈和算符栈。
2.定义了一个z[Max]数组用来存放出栈的“（”的算符值，以避免将数据初值0入栈而导致出错。
（二）模块接口设计：1.各函数原型为：void main() /*主函数*/int menu() /*菜单函数*/void suanshi() /*计算四则运算表达式*/ SeqStack *Init_SeqStack() /*栈初始化*/int Push_SeqStack (SeqStack *s, int x) /*入栈*/int Pop_SeqStack(SeqStack *s, int *x) /*出栈*/int Top_SeqStack(SeqStack *s) /*取栈顶元素*/int Empty_SeqStack(SeqStack *s) /*判断是否为空栈*/2.系统界面切换的实现利用清屏函数system("cls")实现屏幕切换，在从本界面返回上一界面时，根据提示输入即可，例如：printf("是否继续查询,输入y或Y继续,输入其他键返回上一菜单\n");scanf("%c",&choice);if(choice=='y'||choice=='Y') suanshi();则输入输入任意键都能返回上一界面，在main（）函数中用for的无穷循环语句实现各函数的循环调用，以使各功能能够重复实现，直至用户退出系统为止。
（三）盒图：1.主函数盒图图2 主函数盒图2.菜单函数盒图3.算术求值函数盒图调用清屏函数system(“cls ”)输出请输入一个带有括号的四则运算的算式以#结束:输入一个四则运算表达式存入a1数组中 令p 指针指向a1数组，设置对象栈s1和算符栈s2取第一个字符存入变量c 中 当c 不为空时 ‘0’=<c<=’9’是否 a=a*10+c-'0'‘#’ ‘+’ ‘-’ ‘*’ ‘/’ ‘(’ ‘)’x=0;e2=-1;f=-1 x=1;e2=1;f=1x=2;e2=1;f =1x=3;e2=2;f=2x=4;e2=2;f =2x=5;e2=0;f =4x=6;e2=-1;f=-1 x!=5&&z[i-1]==0是否将a 入对象栈，a=0i++如果算符栈空或者栈外优先级高于栈外，则将算符入栈否则将对象栈中出栈两个数据，算符栈出栈一个算符进行计算，直到栈内优先级高于栈外将中间结果入对象栈 算符栈为空是否跳出循环将算符出栈，若为‘（’，且x=‘）’，则将其出栈，否则修改优先级如果x!=6&&x!=0，则将x 入算符栈，并设置优先级c=*p++输出结果并输出是否继续查询,输入y 或Y 继续,输入其他键返回上一菜单 choice=输入字符，若choice==’y ’||’Y ’,则递归调用suanshi(),否则返回4.入栈函数盒图图5 入栈函数盒图四、调试分析在调试过程中我遇到的问题以及我的采取措施有：（一）我先编写只含有加减的运算表达式，然后把乘除加进来，最后再把括号加进来。
因为加减的优先级相同，所以一刚开始，我并没有用栈来做，而是用数组来做，我设置了一个整数类型的数组用来保存表达式中的数值，一个字符类型的数组用来保存算符，然后从左往右依次计算即可，因此，没有什么大问题。
在将乘除加进来的时候，由于涉及到优先级的问题，因此，我不得不将对象数组和算符数组转换为对象栈和算符栈。
当我把括号加进来的时候，就遇到了将初值0数据多次入栈而导致出错的现象，所以，我设置了一个z[Max]数组用来存放“（”出栈时的值，从而解决了问题。
（二）在接收用户输入的数据的时候，我用了整型数据来接收，这样在做除法运算的时候，就有可能会出现运算结果与预期结果不相符的情况，比如1/2,在本系统中运行的结果为0，但是我们预期的结果应该是0.5。
但是如果将栈中的数据元素定义为实型，当将出栈的元素放入switch-case语句中时，系统又会报错。
由于时间原因，我并没有对此做修改，还是将栈中的数据元素定义为整型，但是这样可能会导致在做除法运算的时候，出现结果不准确的情况，这也是本系统的一个漏洞。
（注：本系统的所有代码都是在windows环境下的Microsoft Visual C++ 6.0编译器中运行的。
）五、用户手册（一）进入系统双击算术表达式求值系统.cpp文件，按compile键（或Ctrl+F5）编译程序，再按BuildExecute键（或Ctrl+F5）运行程序，然后就进入了算术表达式求值系统；也可以直接在Debug中找到算术表达式求值系统.exe文件，然后双击它，直接进入系统。
（二）求表达式之值1.进入系统后，输入“1”，按回车，即进入算式表达式求值界面，若输入了除“1”和“2”以外的其他键，则会出现输入错误的提示信息，再按一次回车将重新回到菜单界面。
2.输入一个表达式以“#”为结束标志，要求输入的所有数据都为整数，且只能输入四则运算的算式，即算式中只含有+、-、*、/以及括号，如输入（12+3）*2+9*4#，按回车，即能得到结果。
3.如果想继续进行计算，则可以输入“y”或“Y”，然后重复步骤2，输入其他键将返回上一菜单。