《什么是前缀表达式.doc》由会员分享，可在线阅读，更多相关《什么是前缀表达式.doc（4页珍藏版）》请在三一文库上搜索。
1、什么是前缀表达式前缀表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。 编辑本段前缀表达式如何求值对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例如，前缀表达式“- 1 + 2 3“的求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到
2、+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，并继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。 编辑本段前缀表达式有什么用处前缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单的操作就能得到运算结果的表达式。例如，(a+b)*(c+d)转换为*,+,a,b,+,c,d。它的优势在于只用两种简单的操作，入栈和出栈就可以解决任何中缀表达式的运算。其运算方式为：如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将
3、结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。 编辑本段中缀表达式转换为前缀表达式的一些例子a+b - +,a,b a+(b-c) - +,a,-,b,c a+(b-c)*d - +,a,*,-,b,c,d a=1+3 - a=+,1,3 编辑本段中缀表达式转换为前缀表达式的一般算法(1) 首先构造一个运算符栈(也可放置括号)，运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。 (2)从右至左扫描中缀表达式，从右边第一个字符开始判断： 如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。 如果是运算符，则比较优先级。如果当前运算符的优先级大
4、于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，再将当前运算符入栈。 如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇右括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。 (3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆序输出字符串。中缀表达式也就转换为前缀表达式了。 实例分析将中缀表达式“1+(2+3)*4)-5”转换为前缀表达式。 中缀表达式 后缀表达式 运算符栈 说明 5 5 空 5，是
5、数字串直接输出 - 5 - -，栈内无运算符，直接入栈) 5 - ) )，直接入栈 4 5 4 - ) 4，是数字串直接输出 * 5 4 - ) * *，栈顶是括号，直接入栈 ) 5 4 - ) * ) )，直接入栈 3 5 4 3 - ) * ) 3，是数字串直接输出 + 5 4 3 - ) * ) + +，栈顶是括号，直接入栈 2 5 4 3 2 - ) * ) + 2，是数字串直接输出 ( 5 4 3 2 + - ) * (，参考 ( 5 4 3 2 + * - (，参考 + 5 4 3 2 + * - + +，优先级大于等于栈顶运算符，直接入栈1 5 4 3 2 + * 1 - + 1
6、，是数字串直接输出 空 5 4 3 2 + * 1 + - 空 描扫结束，将栈内剩余运算符全部出栈并输出空 - + 1 * + 2 3 4 5 空 逆序输出字符串 编辑本段各运算符及符号优先级)：直接入栈 (：遇)前，将运算符全部出栈并输出；遇)后，将两括号一起删除 +、-：1 *、/、%：2 ：3后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *,即(2 + 1) * 3 编辑本段表达式的计算运用后缀表达式进行计算的具体做法： 建立一个栈S 从左到右读后缀表达式，读到数字就将它转换为数值压入栈S
7、中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中 如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束 编辑本段表达式之间的转换计算机实现转换： 将中缀表达式转换为后缀表达式的算法思想： 开始扫描； 数字时，加入后缀表达式； 运算符： a. 若为最高级的运算符，入栈； b. 若为 (，入栈； c. 若为 )，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除( ； d. 若为不是最高级的运算符，则将从栈顶到第一个优先级不大于（小于，低于或等于）它的运算符（或 (,但优先满足前一个条件）之间的运算符加入后缀表达式中
8、，该运算符再入栈； 这句话不好理解，可以说成这样，从栈顶开始，依次弹出比当前处理的运算符优先级高的运算符，直到一个比它优先级低的或者遇到了一个左括号就停止。 当扫描的中缀表达式结束时，栈中的的所有运算符出栈； 人工实现转换 这里我给出一个中缀表达式：a+b*c-(d+e) 第一步：按照运算符的优先级对所有的运算单位加括号：式子变成了：(a+(b*c)-(d+e) 第二步：转换前缀与后缀表达式 前缀：把运算符号移动到对应的括号前面 则变成了：-( +(a *(bc) +(de) 把括号去掉：-+a*bc+de 前缀式子出现 后缀：把运算符号移动到对应的括号后面 则变成了：(a(bc)* )+ (
9、de)+ )- 把括号去掉：abc*+de+- 后缀式子出现 发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。如表达式：3+(2-5)*6/3 后缀表达式 栈 3 + 3 +( 3 2 +(- 3 2 5 - + 3 2 5 - +* 3 2 5 - 6 * +/ 3 2 5 - 6 *3 +/ 3 2 5 - 6 *3 /+中缀表达式中缀表达式（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。中缀表达式是人们常用的算术表示方法。 与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。 与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。