前缀后缀算术编程.doc

一、设计思想 中缀转化为后缀算法过程中要使用一个栈和两个数组，（栈用来存放运算符，一个数组用来存放中缀表达式，两一个则是存放后缀表达式）表达式的转换过程如下： （1）、将表达式开始符“#“压入运算符栈，作为栈底元素。 （2）、从左到右依次扫描中缀表达式的每一个字符。 （3）、如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕 （4）、即将进栈的操作符要与栈顶的操作符进行优先级比较，若当所遇到的操作符的优先级大于栈顶元素时，进栈，否则是将栈顶元素一次弹栈放入后缀数组，直到比较操作符小于或等于栈顶元素时为止。重复以上操作，最后将栈内所有操作符放进后缀数组内。 （5）、重复上述步骤直到缀表达式的结束符标记“#“，弹出栈中所有元素并放入后缀表达，转换结束。 中缀表达式为：17-3*4+（8/2）# 后缀表达式为：17 3 4 * - 8 2/+ 中缀转化为前缀算法过程中要使用三个数组，（一个栈数组，一个存放中缀表达式，一个存放前缀表达式）表达式的转换过程如下： （1）将表达式开始符“#“压入运算符栈数组，作为栈底元素。 （2）、从右到左依次扫描中缀表达式的每一个字符。 （3）、如果遇到的是开括号“）”，则将它们放进栈数组内（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“（”时，将栈中的元素弹出来并放入前缀表达式中，直到栈顶元素为“）”时，将栈顶元素“）”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕 （4）、如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到操作符的优先级大于或等于栈顶元素的优先级的时则将它压入栈中。 （5）、重复上述步骤直到缀表达式的结束符标记“#“，弹出栈中所有元素并放入前缀表达，输出倒序输出。转换结束。 中缀表达式：17-3*4+（8/2）# 转换前缀表达式+-17 *3 4 /8 2 后缀表达式的计算： 、从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到的是符号，就将栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。 例如：后缀表达式17 3 4 * - 8 2 /+ 首先计算*左边的3 4 即3*4得出的结果放入栈中，再算—左边的17 12 - 得到的结果5再放进栈，一次类推，最后结果9. 前缀表达式的计算： 、从右到左遍历表达式的每个数字和符号，遇到是数字就进栈，遇到的是符号，就将栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。 例如：前缀表达式+ - 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 s[N],char p[N]) //将中缀表达式转化为前缀表达式 { char stack[N]; int top=0,j=0, len=0; if(s[0]==)) { printf(对不起，您输入不合法，将退出当前的程序！); printf(\n\n); } else { while(s[len]!=\0) { len++; } for(int i=len-1;i=0;) { if(s[i]=48 s[i]=57) { while(s[i]=48 s[i]=57)