《[计算机软件及应用]插入运算符使表达式成立课程设计实验报告(word文档良心出品).doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]插入运算符使表达式成立课程设计实验报告(word文档良心出品).doc（35页珍藏版）》请在金锄头文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告2009 2010 学年第 二 学期课程 数据结构与算法课程设计名称插入运算符等式成立问题学生姓名王见学号0804012018专业班级08计本（2）班指导教师王昆仑2010 年 6 月课程设计题目123456789=a,在等式的左边任意两个数字之间插入+、-、*，使得等式成立，输出所有算式。如 123-45-67+89=100。一、 问题分析与任务定义1问题分析在等式左边123456789的任意两空之间插入+、-、*，也就是说首先这些数字的先后顺序不能改变。其次，123456789，八个位置可以任意插入三种符号，还有一种情况就是不插，这样把无符号也看成一种
2、插入情况，便问题就变成这八个位置插入四种符号的问题，初步估算存在48=65536种算式。a的分析，123456789八个位置插入不同的符号后便会出现不同的结果，但是在众多的算式中也会出现相同的结果，另一种方式来解释就是对于给定一个结果a，可以求出算式。算式虽多，但是有的结果也不一定会出现，对于一些a的给定值不一定就能有算式。2任务定义a是可以任意取得，所以我们把问题从123456789=a插符号等式成立问题转变为123456789任意两个位置之间插入符号求结果。所以我们的任务是：首先解决怎么样插入符号求出所有表达式，然后就是表达式求值问题。3原始数据输入输出格式对于原始数据的输入输出格式问题规
3、定中并没有明确给出，但是由于这里只需要输入a的值，a的值肯定是一个整型的数，只要输入整型数即可。对于输出，有可能对于给定的a值有很多种算式，这样就应该用列表来整齐的列出。同时也有可能没有算式成立，这就要求在没有算式符合条件的时候作出提醒。4程序应能达到的功能对于任一输入的a值，通过计算能求出所有表达式结果等于a的情况，并且能列出所有符合条件的表达式。如果没有符合条件的提示无计算式。5测试用例输入1234，预测结果：1+234*5-6+78-9=1234，1234-5-67+8*9=1234，1234+5+67-8*9=1234。输入100。输入 1000。输入c，结果预测：提示输入不合法。二、
4、 数据结构的选择和概要分析1.数据结构的选择 表达式的存储结构选用字符型数组。在求表达式的时候，应该是从1开始到9结束，循环进行的。我们必须设置一个结构来存储它，我想到用队列、链表，因为这样可以一个个的入队（插入链表），最后从队列（链表）中获取表达式信息。但是，仔细一想用个数组也可以实现存储，由于同时需要存储符号，所以选用字符型数组。 在计算过程中选用栈作为存储结构。表达式求值，如果不存在*，不需要任何结构来存储，直接用S存储数据进来计算后的结果即可，但是这里牵涉到符号运算的优先级问题。例如计算1+2*3-4#，用栈解决：+ *1 2 1 3 -1进数据栈 *与+比较，2进栈 +进符号栈 *入
5、符号栈数据栈 符号栈 数据栈 符号栈 数据栈 符号栈 7 遇#，所有 -与*比较，2与*出栈计算，与+ 的出栈计算 比较，1和+出栈计算后入栈 数据栈 符号栈 数据栈 符号栈 图3-1栈解决表达式计算的示意图这样结果就出来了，1+2*3-4=3。就是因为栈有着先进后出的特点，所以在运用栈存储表达式时不会打乱表达式的顺序。所以栈是最好的选择。我们再从空间性能上考虑，栈在存储表达式的时候，一边运算一边进出栈，而每个栈中最多不会超过两个元素，两个栈最多才占4个单位空间。而如果我们用链式结构来存储，需要的指针就要占几个单位空间了，再加上链式结构是先存储整个表达式再计算，空间上开销很大。从时间性能上考虑
6、，每个数据进入时，又进栈有出栈，而用链式结构，也是有入有出，所以整体上来说，时间性能差不多。因此当然选用栈作存储结构。2.数据结构的定义 表达式的存储数组的定义char strmaxlen; 表达式存储栈定义#define maxlen 20/数字栈结构定义typedef structint stackmaxlen;/存储数字int top;stack2;/数字栈/符号栈结构定义typedef struct char stackmaxlen;/存储符号int top;stack1;3.主要算法流程 单次求表达式的算法流程经过i循环 j+n%4=2符号op=-符号op=* 符号op=+符号入数组
7、数字入数组n=n/4n%4=1n%4=0 m=m*10+j定数组下标为0把1先入数组strj=2j=9到单次求表达式出入栈入栈N YN YYNYN YNY注：op进入的符号，str是存储表达式的数组，ptr是指示str数组的第几个位置n表示第n个表达式，j表示从当前数字（2-9），m是j的前一数字（0-8）图3-2一次求表达式算法流程图 单次求表达式值的出入栈算法流程 s=m出栈计算，s为计算结果s 入OPND栈，op入OPTR m = j j +判断栈顶是*判断op为*m 入OPND栈，原来的栈顶元素入OPTR栈判OPND为空进入的m入OPNDop 入OPTR判OPTR中有两个不为*的元素用
8、n%4求余的方式判断进入的符号opj=9初始m=1,从2开始求表达式算法求最终结果算法图3-3单次求表达式值的出入栈算法 求最终结果算法 单次求表达式值算法判OPND为空 s=mOPND中有一个元素各出栈一次和现有m运算，最后结果为sOPTR栈顶元素为*两栈都出栈两次，栈中元素运算后再与m进行运算，结果为s两栈都出栈一次，和现有m进行计算，再各出栈一次，计算最终结果sNYNYNY输出这一次的表达式及结果图3-4求最终结果算法流程图 完整的算法流程 开始i=0i65536单次求表达式值的出入栈算法 单次求表达式算法 求最终结果算法 输出表达式及结果 i +; NY图3-5完整算法流程图三、 详细
9、设计与编码1.求表达式算法设计我们首先来分析一下十进制转化为二进制的过程，例如N=9:9%2=1,9/2=4;4%2=0,4/2=2;2%2=0,2/2=1;1%2=1,1/2=0;于是，我们得到二进制数为：00001001。说明我们可以用n%2，n/2的方式来求二进制数。我们得到的启发是，用同样的方法可以求出四进制码。例如求N=11:11%4=3,11/4=2; 2%4=2,2/4=0; 于是得到11的四进制码为：00000023。二进制是由0、1组成是因为任何数与2求余为0或1，同理，四进制数是由0、1、2、3组成。我们再思考1_2_3_4_5_6_7_8_9插符号问题，9个数字中间存在8
10、个可以插符号的位置。假如我们设定：0表示无符号，1表示+，2表示-，3表示*。我们就可以定义出8个位置的48个不同的组合。比如1+2+3-45*67+89，我们可以用11203010来表示这个表达式的符号组合。例如：1+2+3-45*67+8911203010 图4-1表达式符号的八位四进制表示我们这样来求表达式：例如第123种组合，即n=123。Str来存储表达式str1=1123%4=3， op=*,str2=*, 123/4=30;30%4=2, op=-,str3=2,str4=- , 30/4=7;7%4=3, op=*,str5=3 ,str6=*, 7/4=1;1%4=1, op
11、=+,str7=4,str8=+, 1/4=0;0%4=0, m=5*10+6=56, 0/4=00%4=0, m=56*10+7=567, 0/4=00%4=0, m=567*10+8=5678, 0/4=00%4=0, m=5678*10+9=56789, 0/4=0;str8=56789根据我们计算的先后，我们所得的表达式为：1*2-3*4+56789，同时我们所得到的二进制码（按顺序排）32310000。验证时一一对应的关系，但是发现一下问题是：我们不能完全按照四进制码的求法规则来办，我们要根据所求的四进制码的每一位的先后顺序来对照。再来分析一下这种方法的好处：我们来算一下求表达式的过
12、程的时间复杂度和空间复杂度，我们将123456789数字的位数定为n，则i的取值最大为4n-1，所以求表达式的时间复杂度函数T(n)=n*4n-1,即时间复杂度为O(n*22n)。空间上，每个表达式最多是n个数字n-1个符号即2n-1个单位空间，而最少是n个字符没有符号即n个单位空间，所以平均空间复杂度函数：S(n)=(3n/2)* 4n-1，所以平均空间复杂度是：O(n*22n)。假设利用n重循环来解决这个问题的话，时间复杂度函数是：T(n)=n*4n-1，时间复杂度是O(n*22n)；再从空间上考虑，首先运用的循环变量就多了n-1个，存储空间也就占了n-1个单位空间，在一个位置上有无符号都要占一个空间，所以每次都占2n-1个空间，总共有占3n-2个空间，空间复杂度函数：S(n)= (3n-2)* 4n-1
