表达式求值

表达式求值,什么是表达式 ?,表达式,是由数字、运算符、数字分组符号(如括弧)、自由变数和约束变数等以能求得数值的有意义排列方法所得的组合。表达式是一个递归的定义，表达式中可以蕴含表达式。,表达式的基本形式：,S1 + OP + S2,（中缀表达式）,表达式的另外两种形式：,OP + S1 + S2 （前缀表达式）,S1 + S2 + OP（后缀表达式）,前缀、中缀、后缀表达式,中缀表达式： 运算符放在两个运算对象中间。如：(A+B)*C；,后缀表达式： 运算符在式中出现的顺序恰为 表达式的运算顺序;每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。如：AB + C *；,前缀表达式： 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式。如： * + AB C ；,为何产生三种不同的表达式形式 ？,中缀表达式易于阅读，符合人类思维习惯前缀表达式与后缀表达式，都是用操作符的顺序来代替优先级，可以舍弃括号等概念，化繁为简后缀表达式不同于前缀表达式的一点：操作数在前，操作符在后。 这在计算机编程中更容易实现,后缀表达式的计算,运用后缀表达式进行计算的具体做法：建立一个栈S 从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中 如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束,如何从后缀表达式求值,先找运算符 再找操作数,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,a,b,e,axb,c,d,d/e,c - d/e,f,(c - d/e)*f,a*b+(c-d/e)*f,ab+(c-d/e)f,但我们已经习惯了中缀表达式。以上思想只解决了计算后缀表达式的问题。能否将我们熟悉的中缀表达式转化为后缀表达式呢？ 能,将中缀表达式转换为后缀表达式的算法思想,设立操作符栈,栈底为“#”当读到数字直接送至后缀式队列中 当读到运算符t时， a. 将栈中所有优先级高于或等于t的运算符弹出，送到后缀式队列中； b. t进栈 读到左括号时总是将它压入栈中 读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至后缀式队列后，再丢弃左括号。,中缀表达式转后缀表达式示例,7*5-(8+(3+4)/7)#,#,操作数：输出操作符 t ：a. 将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中b. t进栈 左括号：压入右括号：将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号,7,5,8,3,4,7,*,+,+,*,(,(,-,（转换后的后缀表达式）,-,+,/,+,/,表达式计算实现的总结,通过以上分析，可得出对一般表达式（中缀表达式）进行计算的思路：将中缀表达式串转换为后缀表达式对转换后的后缀表达式进行计算,能否对一个中缀表达式直接进行计算呢 ？,分析：表达式计算涉及两个过程表达式转换过程表达式计算过程两个过程分别使用不同的栈：操作符栈操作数栈,中缀表达式直接计算思路,设立操作符栈(a)和操作数栈(b)设表达式的结束符为“#”,a栈的栈底为“#”；若当前字符串是个操作数，则直接压入b栈。 (设当前运算符为t) 否则：若t的优先级别高于a栈栈顶运算符，则压入a栈 否则：若t的优先级别低于或者等于a栈栈顶运算符，则将栈中 所有优先级高于或等于t的运算符弹出 (对于括号的处理规则与中缀转后缀的规则一致) a栈每弹出一个运算符(除括号)，则b栈弹出离栈顶最近的两个操作数进行计算，并将计算结果压入b栈中Goto Step III,中缀表达式直接计算示例,6 * 3（4 + 2）#,6,*,3,4,+,(,2,优先级低于*,计算: 6*3,18