前缀后缀算数运算编程.doc

一、设计思想1、 中缀转化为后缀算法过程中要使用一个栈和两个数组，（栈用来存放运算符，一个数组用来存放中缀表达式，两一个则是存放后缀表达式）表达式的转换过程如下：（1）、将表达式开始符“#“压入运算符栈，作为栈底元素。（2）、从左到右依次扫描中缀表达式的每一个字符。（3）、如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕（4）、即将进栈的操作符要与栈顶的操作符进行优先级比较，若当所遇到的操作符的优先级大于栈顶元素时，进栈，否则是将栈顶元素一次弹栈放入后缀数组，直到比较操作符小于或等于栈顶元素时为止。重复以上操作，最后将栈内所有操作符放进后缀数组内。（5）、重复上述步骤直到缀表达式的结束符标记“#“，弹出栈中所有元素并放入后缀表达，转换结束。中缀表达式为：17-3*4+（8/2）# 后缀表达式为：17 3 4 * - 8 2/+2、 中缀转化为前缀算法过程中要使用三个数组，（一个栈数组，一个存放中缀表达式，一个存放前缀表达式）表达式的转换过程如下：（1）将表达式开始符“#“压入运算符栈数组，作为栈底元素。（2）、从右到左依次扫描中缀表达式的每一个字符。（3）、如果遇到的是开括号“）”，则将它们放进栈数组内（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“（”时，将栈中的元素弹出来并放入前缀表达式中，直到栈顶元素为“）”时，将栈顶元素“）”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕（4）、如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到操作符的优先级大于或等于栈顶元素的优先级的时则将它压入栈中。（5）、重复上述步骤直到缀表达式的结束符标记“#“，弹出栈中所有元素并放入前缀表达，输出倒序输出。转换结束。中缀表达式：17-3*4+（8/2）# 转换前缀表达式+-17 *3 4 /8 23、 后缀表达式的计算：（1） 、从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到的是符号，就将栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。 例如：后缀表达式17 3 4 * - 8 2 /+ 首先计算*左边的3 4 即3*4得出的结果放入栈中，再算左边的17 12 - 得到的结果5再放进栈，一次类推，最后结果9.4、 前缀表达式的计算：（1） 、从右到左遍历表达式的每个数字和符号，遇到是数字就进栈，遇到的是符号，就将栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。例如：前缀表达式+ - 17 * 3 4 / 8 2 首先从最右边开始，计算/最近的两位数计算得4，再放进栈中，再算*3 4，得12放进栈，这时+-17 12 4 以此类推，+5 4 得9，最后结果9.二、算法流程图这部分要画出每个算法的流程图，并对每个流程图用文字简单说明。文字用5号字，宋体。文档中的所有图片要设置为居中，图下面要有图号和图名，图号和图名小5字，居中。如下所示。图1 xxxx算法流程图三、源代码下面是中缀转换前缀表达式int f(char c) /判断运算符级别函数； int f=-1; switch(c) case+: case-:f=1;break; case*: case/:f=2;break; default:f=0;break; return f;int Operator(char c) /判断字符是否为操作符 if(c=+|c=-|c=*|c=/) return 1; else return 0;void convert(char sN,char pN) /将中缀表达式转化为前缀表达式 char stackN; int top=0,j=0, len=0; if(s0=) printf(对不起，您输入不合法，将退出当前的程序！); printf(nn); else while(slen!=0) len+; for(int i=len-1;i=0;) if(si=48 & si=48 & si=f(stacktop) top+; stacktop=si;break; else pj=stacktop; top-;j+; if(si=() /假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 while(stacktop!=) pj=stacktop; top-;j+; top-; i-; while(top!=0) /假如输入完毕，栈中剩余的所有操作符出栈并加到输入串中 pj=stacktop; j+; top-; pj=0; printf(转化成对应的前缀表达式为: ); for(;j=0;j-) printf(%c,pj); printf(nn); 下面是后缀表达式求值函数int calculator(char s,int n) /计算表达式的值 int i,x1,x2,x; intstack *q; q=intcreat(); for(i=0;i=n;i+) if(si= ) i=i+1; if(si=0) x1=(int)si-48; while(si+1=0) x1=10*x1+(int)si+1-48; /多位数求值方法 i=i+1; q=intpush(q,x1); else if(si=+) x2=inttop(q); q=intpopl(q); x1=inttop(q); q=intpopl(q); q=intpush(q,x1+x2); else if(si=-) x2=inttop(q); q=intpopl(q); x1=inttop(q); q=intpopl(q); q=intpush(q,x1-x2); else if(si=*) x2=inttop(q); q=intpopl(q); x1=inttop(q); q=intpopl(q); q=intpush(q,x1*x2); else if(si=/) x2=inttop(q); q=intpopl(q); x1=inttop(q); q=intpopl(q); q=intpush(q,x1/x2); x=inttop(q); return x;四、运行结果图5算术表达式运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 问题1描述 无法区分一位数和多位数，及计算有误。 解决方法：在每个完整的数之间用空格分开，并且添加语句，主要思想是当第一个数字进栈后，下一个进栈的数组元素若是数字则进栈，若是运算符，则加空格将其分开，在前缀表达式求值语言中加入一下代码：if(si=0) x1=(int)si-48; while(si+1=0)x1=(int)si+1-48) * pow(10,j)+x1; i=i+1;j+; 这里引用了数学里pow()函数，很方便计算多位数。l 问题2描述 当输入带（）的表达式出现错误，进栈弹栈不正确。解决方法：分析运算符进栈的优先级，（）优先级最低，但要明确在后缀表达式时，即将进栈的运算符优先级栈顶元素则进栈，而前缀表达式时，即将进栈的运算符=栈顶元素则进栈。六、心得体会这次实验设计让我加深了C语言程序设计一些重要知识和这个学期学到的数据结构实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。并且老师的提问更让我学到很多东西，对于一个编程者来说，编程思想很重要，不但要实现算法，而且要简洁，提高运算效率，程序的健壮性，稳定性尤其重要。在程序设计过程中让我有心注意到得是，细心非常重要，一个标点就可能使得整个程序无法进行，在所有代码中避免不了输出字，比如数字1跟字母l很难区别，眼睛看的很像，机器判断是错，但是人眼看的一样，缺少），等类似这些问题。 程序设计时，也不要怕