插入运算符等式成立问题-数据结构与算法课程设计报告

1、合肥学院计算机科学与技术系课程设计报告2009 2010 学年第 二 学期课程数据结构与算法课程设计名称插入运算符等式成立问题学生姓名王见学号0804012018专业班级08计本（2）班指导教师王昆仑2010 年 6 月课程设计题目123456789=a,在等式的左边任意两个数字之间插入 +、 -、* ，使得等式成立，输出所有算式。如 123-45-67+89=100。一、问题分析与任务定义1问题分析在等式左边 123456789 的任意两空之间插入 +、- 、* ，也就是说首先这些数字的先后顺序不能改变。其次， 1 2 3 456789， 八个位置可以任意插入三种符号， 还有一种情况就是不插

2、， 这样把无符号也看成一种插入情况， 便问题就变成这八个位置插入四种符号的问题，初步估算存在 48=65536 种算式。a 的分析， 123456 789 八个位置插入不同的符号后便会出现不同的结果， 但是在众多的算式中也会出现相同的结果， 另一种方式来解释就是对于给定一个结果 a，可以求出算式。算式虽多，但是有的结果也不一定会出现，对于一些 a 的给定值不一定就能有算式。2任务定义a 是可以任意取得，所以我们把问题从 123456789=a 插符号等式成立问题转变为 123456789 任意两个位置之间插入符号求结果。所以我们的任务是：首先解决怎么样插入符号求出所有表达式，然后就是表达式求值

3、问题。3原始数据输入输出格式对于原始数据的输入输出格式问题规定中并没有明确给出，但是由于这里只需要输入 a 的值， a 的值肯定是一个整型的数，只要输入整型数即可。对于输出，有可能对于给定的 a 值有很多种算式，这样就应该用列表来整齐的列出。同时也有可能没有算式成立，这就要求在没有算式符合条件的时候作出提醒。4程序应能达到的功能对于任一输入的a 值，通过计算能求出所有表达式结果等于能列出所有符合条件的表达式。如果没有符合条件的提示无计算式。5测试用例a 的情况，并且输 入1234 ， 预 测结 果： 1+234*5-6+78-9=1234 ， 1234-5-67+8*9=1234 ，1234+

4、5+67-8*9=1234。输入 100。输入 1000。输入 c，结果预测：提示输入不合法。二、数据结构的选择和概要分析1. 数据结构的选择 表达式的存储结构选用字符型数组。在求表达式的时候，应该是从 1 开始到 9 结束，循环进行的。我们必须设置一个结构来存储它，我想到用队列、链表，因为这样可以一个个的入队（插入链表），最后从队列（链表）中获取表达式信息。但是，仔细一想用个数组也可以实现存储，由于同时需要存储符号，所以选用字符型数组。 在计算过程中选用栈作为存储结构。表达式求值，如果不存在* ，不需要任何结构来存储，直接用S 存储数据进来计算后的结果即可， 但是这里牵涉到符 号运算的优先级

5、 问题。例如计算1+2*3-4# ，用栈解决：1 进数据栈*与+比较，2 进栈*+进符号栈2*入符号栈+11数据栈符号栈数据栈符号栈数据栈符号栈遇# ，所有-与*比较，2 与*出栈计算，与+的出栈计算比较，1 和+出栈计算后入栈37-数据栈符号栈数据栈符号栈图 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. 主要算法流程 单

7、次求表达式的算法流程经过 i 循环定数组下标为0把 1 先入数组strj=2j=9Yn%4=0YYm=m*10+j符号入数组到单次求表达式N出入栈入栈NNn%4=1Yn%4=2N符号op=+Y符号op=-N符号op=*Y数字入数组n=n/4j+注： op 进入的符号，str 是存储表达式的数组， ptr 是指示 str 数组的第几个位置 n 表示第n 个表达式， j 表示从当前数字（ 2-9 ），m 是 j 的前一数字（ 0-8 ）图 3-2 一次求表达式算法流程图单次求表达式值的出入栈算法流程求表达式算法初始 m=1,从 2 开始求最终结果算法j=9用 n%4 求余的方式判断进入的符号 op

8、判 OPND 为空判 OPTR 中有两个进入的 m 入 OPND不为 *的元素op 入 OPTRm 入 OPND 栈，原来的栈顶判断 op 为 *元素入 OPTR 栈判断栈顶是 *出栈计算， s 为计s=m算结果s 入 OPND 栈， op 入 OPTRm = jj +图 3-3 单次求表达式值的出入栈算法 求最终结果算法单次求表达式值算法判 OPND 为N空YOPND中 有N一个元素s=mY各出栈一次和现有m 运算，OPTR栈顶元N最后结果为s素为 *Y两栈都出栈两次， 栈中元素运算后再与m 进行运算，结果为 s两栈都出栈一次，和现有 m 进行计算，再各出栈一次，计算最终结果 s输出这一次的

9、表达式及结果图 3-4 求最终结果算法流程图 完整的算法流程开始i=0Ni65536Y单次求表达式值的出入栈算法单次求表达式算法求最终结果算法输出表达式及结果i +;图 3-5 完整算法流程图三、详细设计与编码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=

10、0;,于是得到 11 的四进制码为： 00000023。二进制是由 0、 1 组成是因为任何数与 2 求余为 0 或 1，同理，四进制数是由 0、1、2、3 组成。我们再思考 1_2_3_4_5_6_7_8_9 插符号问题， 9 个数字中间存在 8 个可以插符号的位置。假如我们设定： 0 表示无符号， 1 表示+，2 表示- ，3 表示 * 。我们就可以定义出 8 个位置的 48个不同的组合。 比如 1+2+3-45*67+89，我们可以用 11203010 来表示这个表达式的符号组合。例如：1+2+3-45*67+8911203010图 4-1 表达式符号的八位四进制表示我们这样来求表达式：

11、例如第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=+ ,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根据我们计算的先后，我们所

12、得的表达式为： 1*2-3*4+56789 ，同时我们所得到的二进制码（按顺序排） 32310000。验证时一一对应的关系，但是发现一下问题是：我们不能完全按照四进制码的求法规则来办，我们要根据所求的四进制码的每一位的先后顺序来对照。再来分析一下这种方法的好处：我们来算一下求表达式的过程的时间复杂度和空间复杂度，我们将 123456789 数字的位数定为 n，则 i 的取值最大为 4n-1，所以求表达式的时间复杂度函数 T(n)=n*4n-1,即时间复杂度为 O(n*22n)。空间上，每个表达式最多是 n 个数字 n-1 个符号即 2n-1 个单位空间，而最少是 n 个字符没有n-1符号即 n

13、 个单位空间，所以平均空间复杂度函数：S(n)=(3n/2)* 4，所以平均空假设利用 n 重循环来解决这个问题的话， 时间复杂度函数是： T(n)=n*4n-1，时间复杂度是 O(n*22n)；再从空间上考虑， 首先运用的循环变量就多了 n-1 个，存储空间也就占了 n-1 个单位空间，在一个位置上有无符号都要占一个空间，所以每次都占 2n-1 个空间，总共有占 3n-2 个空间，空间复杂度函数： S(n)= (3n-2)* 4n-1,所以空间复杂度为 O(3n-2)* 22n)，空间上用八位四进制码的方式比 8 重循环要省的多。由以上几点，我们可以写出求表达式的算法：/*源码一：求表达式算

14、法*/ for(i=0;i65536;i+)m=1;n=i;ptr=0;strptr+= 1;for(j=2;jm 入 OPND 栈， op 入 OPTR 栈OPTR 栈顶元素为 * 两栈都出栈一次计算op= * m入OPTR 栈顶元素不为 *-s=m栈OPTR 栈顶元素为 *-两栈都出栈一次计算符号栈不为空op!= * OPTR 栈顶元素为 +-两栈都出栈一次计算op 入栈OPTR 栈顶元素为 -两栈都出栈一次计算符号栈中有两个元素同时不为* - 都出栈两次，计算后再入栈。运用程序语言来描述就是：/*源码二：表达式进出栈判断*/if(n%4)switch(n%4) /用 switch 来判断

15、首次进入的是什么符号case 1:op=+;break;/余数为 1 则为 +case 2:op=-;break;/余数为 2 则为 -case 3:op=*;break;/余数为 3 则为 */把三个符号都入栈的情况解决掉if(Getnum2(OPND)=1&Gettop1(OPTR)!=*)opo=Gettop1(OPTR);/提取 OPTR 栈顶元素pop1(OPTR);/OPTR 出栈一次opo1=Gettop1(OPTR);/提取 OPTR 栈顶元素pop1(OPTR);/OPTR 出栈一次s1=Gettop2(OPND);pop2(OPND);s2=Gettop2(OPND

16、);pop2(OPND);if(opo1=+)s=s2+s1;else s=s2-s1;push2(OPND,s);push1(OPTR,opo);/如果栈都为空，那就都入栈if(Isnull2(OPND)=1&Isnull1(OPTR)=1)push2(OPND,m);/m 入栈 OPNDpush1(OPTR,op);/op 入栈 OPTRelse/栈都不为空且不含两个元素，即栈中都含有一个元素的时候if(op=*)/ 当进来的 op 是 * 时if(Gettop1(OPTR)=*)/ 当当前的栈顶元素是 *s1=Gettop2(OPND);s=s1*m;pop2(OPND);pop

17、1(OPTR);else/当前 OPTR 栈顶元素不为 *s=m;else /当进来的 op 不是 * 时if(Gettop1(OPTR)=*)/OPTR 栈顶元素是 *s1=Gettop2(OPND);s=s1*m;pop2(OPND);pop1(OPTR);else if(Gettop1(OPTR)=+)/OPTR 栈顶元素是 +时s1=Gettop2(OPND);s=s1+m;pop2(OPND);pop1(OPTR);else/OPTR 栈顶元素是 - 时s1=Gettop2(OPND);s=s1-m;pop2(OPND);pop1(OPTR);push2(OPND,s);push1(

18、OPTR,op);/*/需要说明的是，由于是在有符号的时候才能进出栈，所以用if（ n%4）来排除无符号的情况，又因为我们不知道起始的时候， 符号 op 到底是什么，因此用 switch语句来判断开始时的 op 值。3. 求最终结果算法设计如果我们仅利用上面的出入栈算法， 到最后再出栈输出结果。 那结果一定是错误的，我们来看一组特殊的情况： 123456789=123456789。它中间没有一个符号，也就是说 n%4 永远是 0，也就不会用到出入栈算法， 所以栈还是空的。 但结果计算不出。所以我们需要考虑在 for（j）循环结束后，栈中余留情况。经过仔细考虑，存在下列几种情况： 1）两栈都为空

19、， 2）两栈都为一个元素并且 OPTR 栈顶为 * ， 3）两栈都为一个元素并且 OPTR 栈顶元素为 +,4) 两栈都为一个元素并且 OPTR 栈顶元素为 - ， 5）两栈都有两个元素， OPTR 栈顶元素为 * ，栈底元素为 +，6）两栈都有两个元素， OPTR 栈顶元素为 * ，栈底元素为 - ，7）两栈都有两个元素， OPTR 栈顶元素为 +，栈底元素为 +，8）两栈都有两个元素， OPTR 栈顶元素为 +，栈底元素为 - ，9）两栈都有两个元素， OPTR 栈顶元素为，栈底元素为 +，10）两栈都有两个元素， OPTR 栈顶元素为 - ，栈底元素为 - 。用示意图表示如下：1*1+O

20、PNDOPTR1 ：两栈都为空OPND2OPTROPND： 两栈都有一个元素并且 OPTR 栈顶为 *OPTR3：两栈都有一元素OPTR 栈顶为 +2*2*1-1+1-OPNDOPTROPNDOPTROPNDOPTR4：两栈都有一个元素5：两栈都有两个元素 OPTR6 ：两栈都有两个OPTR 栈顶为 - 栈顶为 * ，栈底为 +元素， OPTR 栈顶* ，栈底为 -2+2+2-1+1-1+OPNDOPTR7: 两栈都有两个元素OPTR 栈顶为，栈底为OPNDOPTROPNDOPTR8:两栈都有两个元素：两栈都有两个OPTR 栈顶为，栈底元素， OPTR 栈顶为为，栈底为OPNDOPTR10:

21、两栈都有两个元素OPTR 栈顶为，栈底为 - 图 4-2 for( ) 循环后栈中余留情况示意图根据这 10 种情况，利用if , else 语句把它们用程序语言列出来如下：/*源码三：求最后结果算法 */if(Isnull2(OPND)=1&Isnull1(OPTR)=1)/都为空的情况s=m;else if(Getnum2(OPND)=0&Getnum1(OPTR)=0)/ 两栈都有一个元素s1=Gettop2(OPND);pop2(OPND);opo=Gettop1(OPTR);pop1(OPTR);if(opo=*)/ OPTR栈顶为 *s=s1*m;else if(o

22、po=+)/OPTR栈顶为 +s=s1+m;else if(opo=-)/OPTR栈顶为 -s=s1-m;else if(Getnum2(OPND)=1&Getnum1(OPTR)=1)/ 两栈都有两个元素opo=Gettop1(OPTR);pop1(OPTR);opo1=Gettop1(OPTR);s1=Gettop2(OPND);pop2(OPND);s2=Gettop2(OPND);pop2(OPND);if(opo=*)/OPTR栈顶为 *s=s1*m;if(opo1=+)/OPTR栈底为 +s=s+s2;else s=s2-s;/OPTR栈底为 -else if(opo=+)

23、/OPTR栈顶为 +if(opo1=-)/OPTR栈底为 -s=s2-s1+m;else s=s1+s2+m;/OPTR 栈底为 +else/OPTR 栈顶为 -if(opo1=-)/OPTR栈底为 -s=s2-s1-m;else s=s1+s2-m;/OPTR栈底为 +/*/四、上机调试1. 调试问题 问题一：在编好程序来求表达式时，运行，出现结果：FOUND1:123-45-67+89899 烫汤？烫汤$很不明白， 为什么都出现类似错误， 根据经验，这应该是乱码， 可是为什么会出现呢？使用 “断点法” 跟踪程序每一步运行时数组里元素的变化， 刚开始一直都是正确的，一直到 9 运行完，数组里

24、存着 123-45-67+89，一时没有明白。我想过是不是数组的输出时有问题， 于是又检查了一遍， 但这么简单的输出还不至于发生错误。实在不明白的情况下，再次跟踪，发现了严重的问题。在输出时，不仅仅把123-45-67+89 都输出了，而是把 str20中 20 个元素全都输出了，由于后面的 str里没有值便会乱码。而原因在于表达式求完后没有加入停止符。解决方法：在循环外加入 “strptr+= 0”，让0加入， 在读取时，发现 0 就会停止。 问题二：先来看一组数据：FOUND1:123-45-67+89=100FOUND2:12+3*4-56+7+89=100FOUND3:1-2*3-4+

25、5+6+7+89=100FOUND4:12-3-4+5-6+7+89=100FOUND10:1*23-4+5-6-7+89=100我们仔细分析一下：第一组数据和第四组数据是正确的， 第十组数据也是正确的。而第二和第四组数据是错误的。再结合所有结果，发现只要是不含 * 的计算式结果都是正确的 ，而当含有 * 但是 * 只在 +、 -之前出现时，结果也同样是正确的。而如果只要是* 在 +、- 后出现的结果必然错误。再来看看最初的求值方法：if(n%4)if(op= * ) s*=m;else if(op= + ) s+=m;else s-=m;为什么会出现上述情况呢， 经过仔细的观察结果发现， 原

26、来我们可以这么算第三个计算式： 12+3=15，15*4=60 ，60-56=4，4+7=11，11+89=100，也就是从左到右不分符号运算级的计算就是正确的。 再看算法，这么来写也确实证实了观测的结果。所以整个求值算法就是错误的， 要想解决优先级问题， 就得用到一种数据结构来解决，而最应该想到的也就是栈，解决方法就是用栈解决。 问题三加入栈来计算后，先不看结果正确性，发现一个比较奇怪的问题：123456789=-8080892，1+23456789=1， 1-23456789=-1 后面的都是结果很小，很明显的错误。跟踪栈中元素发现：前面的进栈是正确的，而当后面的 56789 因为无符号，

27、 n%4=0，所以 56789 没有经过进栈计算， 所以结果就是前面的数字计算结果。 但是经过仔细思考， 还不仅仅如此， 前面的计算有可能出现多个结果在栈还未运算的现象。解决方法： for(j) 循环外，加入表达式出入栈运算后余留情况的处理，以及和最后一个没有经过栈的数（比如 56789）来进行运算求出最后的结果。这些处理就要根据栈中余留的各种情况来设置不同的处理， 这样就构成了求最后结果的算法。 问题四在对栈的余留问题进行处理后， 结果大部分都是正确的， 但是在每隔几十行就会出现一次明显的错误，结果过小。列出几个错误结果：FOUND:12-3*4+56789=-20FOUND:1+23*4-

28、5+6789=33FOUND:123-45*6-7*8+9=-110FOUND:12345+6*7-89=1356;分析错误结果，发现规律就是两边都是非* ，而中间必有一个 * ，也就是当 * 在 +， -中间时就会发生错误。而可想而知是在出入栈处理时发生了严重的问题。 可是首次出现错误的地方是在四十行，如果运用跟踪法的话， 要按10*40=400 多下才能到达错误的结果，那不是累死了。想着想着，我想通了一个问题，我现在不是在程序中找错，而是要观测错误是为什么，所以我把 i 从 40 开始取，这样第一种情况就是原来的第四十种情况， 跟踪发现错误的地方在表达式出入栈的时候出现混乱，所以没有计算正

29、确。解决方法：情况的种类太多， 要考虑栈中空不空， 几个元素， 栈顶是什么符号，进入的符号是否为 * 号。一下子很容易混乱。所以我决定先在本子上把每一种情况都重新列了一遍， 仔细琢磨有没有落掉什么情况。 最后把这些情况用了判断语句写成了程序。调试没有错误。运行结果也正确了。 问题五在程序的输出格式设计时， 出现一个问题： 我用表格的形式输出结果， 我可以把上边框、下边框和左边框输出，但是不能对齐右边框，如图：经过老师指点， 先计算出表达式的长度， 然后按总长度减去算式表达式长度来算出空格数，用循环来输出空格。最后右边框对齐了。2. 算法性能分析 算法时间性能分析对于求表达式算法， i 最大值是

30、和 j 的最大值有关的， j 最大值是 9 个数，那就有8 个位置，即 i 最大值就是 48，而如果在 12345 中插入符号的话， j 的最大值是 5，这时 i 的最大值就是 44，如果是在 12345n 中插符号， j 的最大值是 n。此时 i 的最大值是 4n-1。所以此算法的时间复杂度是： T(n)=n*4n-1,取 g(n)=n*22n， limT(n)/g(n)=1/4. 因此，该算法时间复杂度是： T(n)=O(n*22n)。对于表达式求值出入栈算法和求表达式是同时进行的， 所以平均时间复杂度也是 O(n*22n)。对于求最后结果的算法中，由于在 for(j) 循环之外，所以平均

31、时间复杂度是 T(n)=4n-1,取 g(n)=22n,limT(n)/g(n)=1/4 ，所以该算法时间复杂度为 :T(n)=O(22n)。 算法空间性能分析设 n 为所取的 j 的最大值。对于求表达式算法，一个表达式最少占有空间 n（无符号的情况），最多占有空间 2n-1（ n-1 个位置全部有符号），平均一下，平均占空间是 3n/2，所以该算法空间复杂度是 :S(n)=(3n/2)*4n-1,取 f(n)=n*22n,limS(n)/f(n)=3/8 。所以复杂度为： O(n*22n)。对于表达式求值出入栈算法， 在单次出入栈时， 每个栈最多用 2 个空间，最少用 0 个空间，平均取 1

32、 个空间。所以 S(n)=n*4n-1*1, 该算法空间复杂度是： O(n*22n)2n对于求最后结果算法，只与i 值有关，所以空间复杂度是：O(2)。程序调试完成了，现在报告也快完成了， 回头想想，当初一拿到程序的时候，我很无奈， 根本就没有头绪， 不知道从何去思考这个问题。 一次在网上看到一篇关于三进制处理类似插符号问题的文章， 从而得到提示。 有了想法，有了解决思路。如果我一直那么的苦想下去到现在还没有思路呢。 所以适当的运用别人的经验来解决问题也是很必要的。此次的设计题目并不长， 但结果却是很多， 要细心是不用说的了。 而在调试过程中出现问题就很难找出问题的原因， 这里我多次的用了断点

33、跟踪的方法， 但是面对六万多种情况， 方法也需要改进，比如说在我发现第四十行有错误的时候，我会把 i 从 40 开始取。这也是我这次设计的一个收获，一次很有用的经验。在面对着存在很多可能性的问题时， 真的很难解决，一不小心就会掉了这种，少了那种。 所以就像教授向我们传授的那样， 我们不急于去写程序， 我们可以把每一种都考虑到， 然后一一列出， 根据我们自己列出的情况， 写程序还不是很容易的事吗。再者，如果有结果不对，我们可以可以考虑我们的列表哪项出了问题。这样就很容易的解决问题了。五、测试结果及其分析1. 输入 1234，结果如下图：图 6-1 结果为 1234 的计算式结果分析：把输出结果与

34、预测结果对比，发现结果一致，达到预测结果。说明算法正确。2. 输入 100，结果如下：（共 78 个算式）图 6-2 结果为 100 的计算式（页1）图 6-3 结果为 100 的计算式（页2）图 6-4 结果为 100 的计算式（页3）图 6-5 结果为 100 的计算式（页4）图 6-6 结果为 100 的计算式（页5）图 6-7 结果为 100 的计算式（页6）结果分析： 由于结果的情况太多， 所以无法预测结果的个数， 但是我们可以计算验证每一种的结果是否正确，随即抽取验证：1+23*4-5+6+7+8-9=1001+234-56-7-8*9=10012-3-4+5*6-7+8*9=10

35、01+2+3+4+5+6+7+8*9=1001*2*3-4+5+6+78+9=100经过随即验证， 没有发现错误的， 因此可以判断结果正确。 我们再来验证结果等于 100 的算式有多少个：3、输入 1000图 6-8 结果为 1000 的计算式结果结果分析：虽然有六万多种情况会得到很多种结果，但也有很多结果是重复的，所以也不是随便输入一个数，就有计算式，这里结果等于1000 的计算式就不存在。所以结果显示该结果无计算式。4. 输入 c , 结果如下：图 6-9 输入 c的显示结果分析： 由于输入的结果不是数字而是字符， 在程序控制中设置了报警， 所以结果显示为这样。5. 验证结果数据个数图 6

36、-10 验证结果数据个数（页1）图 6-11 验证结果数据个数（页2）图 6-12 验证结果数据个数（页3）图 6-13 验证结果数据个数（页4）图 6-14 验证结果数据个数 ( 页 5)图 6-15 验证结果数据个数（页6）验证结果分析：结果算式个数1234567891234567901-23456788123456789134568011,5002073911,4682015112-53714,-6047817439040113910411-13910391139104011814521,表 6-1 算式结果统计表分析：通过修改程序，把程序中相同的结果连续输出，然后统计：1+1+1+1+

37、1+, +20+11+, +20+2+14+, +1+1+1+1+1+1+, =65536从而验证了所得结果的正确性、全面。七、用户使用说明1. 打开文件夹，运行“插入运算符等式成立问题.exe ”。2. 输入你想要得到的结果，结果一定是数字。3.显示一页计算式后，如果还没有完，就会显示任意键翻页。按任意键翻页。4.当出现总计结果有多少个时，表明已经列完所以计算式，任意键就会退出。5. 当输入的不是数字时，就会提示错误。按任意键就会直接退出。八、参考文献1王昆仑，数据结构与算法，中国铁道出版社，2007.62谭浩强， c 程序设计，清华大学出版社， 2005.73 H M Peitel,蒋才鹏

38、等译， C 程序设计教程，机械工业出版社，20004严蔚敏，数据结构：语言版，清华大学出版社，20025胡学钢，数据结构与算法设计指导，清华大学出版社，19996徐士良，常用算法程序集，清华大学出版社，19957关治、陈景良，数值计算，清华大学出版社，19938易大义，计算方法，浙江大学出版社，20079参考网站： http:/ stdio.h#include stdlib.h#include conio.h#define maxlen 20/ 定义符号栈typedef struct char stackmaxlen;int top;stack1;/符号栈/ 定义数据栈typedef stru

39、ctint stackmaxlen;int top;stack2;/数字栈void InitStack1(stack1 *s) /*s-top=-1;初始化stack1 类空栈 */void InitStack2(stack2 *s) /初始化stack2类空栈s-top=-1;int Isnull1(stack1 *s)/判断符号栈是否为空空返回 1，不空返回 0if(s-top=-1)return 1;else return 0;int Isnull2(stack2 *s)/判断数字栈是否为空，空返回1，不空返回 0if(s-top=-1)return 1;elsereturn 0;voi

40、d push1(stack1 *s,char ch)/符号入栈s-top+;s-stacks-top=ch;void push2(stack2 *s,int ch)/数字入栈s-top+;s-stacks-top=ch;void pop1(stack1 *s)/符号出栈s-top-;void pop2(stack2 *s)/s-top-;数字出栈int Getnum1(stack1 *s)/通过top值获取当前栈中元素总数，top=0代表有一个return s-top;int Getnum2(stack2 *s)/return s-top;同 Getnum1char Gettop1(stack

41、1 *s)/获取符号栈中的最上面的符号return s-stacks-top;int Gettop2(stack2 *s)/return s-stacks-top;获取数字栈最上面的数字void main()char op,str30;/op是表示符号， str来存储获得的计算式int i,j,n,m,ptr;long int s;char opo,opo1;/两个变量都是来提取栈中符号的long int s1,s2;/两个变量都是来提取栈中数字的int total;/计算所求的计算式总数int string;/计算式长度int y;/来获取所要求的值long int a;stack1 OPT

42、R1,*OPTR=&OPTR1;/通过定义变量的方式，同时给指针分配内存 stack2 OPND1,*OPND=&OPND1;InitStack1(OPTR);InitStack2(OPND);/初始化两个栈string=1;/ 获取字符的个数，从而控制空格的数量total=0;初始化给 y 一个算式不可能得到的数据，用来控制输入字符时报错y=-80808080;/*美化界面 */system(color 16);/system(mode con: cols=50 lines=50);/*/*通过输入的方式来获取结果*/printf(请输入您要的结果： );scanf(%d,&

43、amp;y);/ 如果输入的是字符， y 不会得到值，所以还是原来的-80808080，通过判断是否为 -80808080 来判断输入是否合法if(y=-80808080)printf( 输入的结果不是数字，为了保护程序，任意键退出 n);system(pause);exit(1);/不合法直接退出printf(n);printf(计算式列表:(每页 15)n);printf( n);/*/*算法开始 */9 个数字 8 个位置，用八位四制码的方式来表示符号， 0 无符号， 1 是+ /2是 - ，3 是 *我们模仿二进制的求法来解决十进制向四进制的转化。因此我们可以用/n%d 得到的余数做为

44、最低位的四进制码，然后 n/4 ，把它向前演化，得到倒数第二位的四进制码。从而来获取各位的四进制码，所以共有 4 的 8 次方种情况。我们求得的四进制码，比如00001023，本来是表示 12345+67-8*9 ，但是为了简便，我们把它倒过来用，最后一位的3 来代表第一位符号，即 1*2-34+56789 ，看上去不一样，情况总数是一样的而且不重复。/*/*解决结果问题 */算式出来了，结果是通过栈来求的，对于符号的优先级问题，我们需要用栈来解决，而在这里的在循环的过程中入栈出栈就存在好多种情况，下面有一一的考虑/*/for(i=0;i65536;i+)/四精制数就是 65536 个s=0;

45、s1=0;s2=0;m=1;n=i;ptr=0;strptr+=1;string=1;for(j=2;j=9;j+)if(n%4)用 switch 来判断首次进入的是什么符号switch(n%4)case 1:op=+;break;case2:op=-;break;case 3:op=*;break;把三个符号都入栈的情况解决掉if(Getnum2(OPND)=1&Gettop1(OPTR)!=*)opo=Gettop1(OPTR);pop1(OPTR);opo1=Gettop1(OPTR);pop1(OPTR);s1=Gettop2(OPND);pop2(OPND);s2=Gettop2(OPND);pop2(OPND);if(opo1=+)s=s2+s1;else s=s2-s1;push2(OPND,s);push1(OPTR,opo);如果栈都为空，那就都入栈if(Isnull2(OPND)=1&Isnull1(OPTR)=1)push2(OPND,m);push1(OPTR,op);/*/如果栈都不为空，分成几种情况考虑如果进来的符号是 * ，则先考虑栈顶符号，也是 * 的话，先出栈运算如果栈顶符号不是 * ，则直接不用计算如果进来的符号不是 *