转化为前缀和后缀表达式882.pdf

前缀、中缀、后缀表达式 前缀、中缀、后缀表达式是对表达式的不同记法，其区别在于运算符相对于操作数的位置不同，前缀表达式的运算符位于操作数之前，中缀和后缀同理。举例：中缀表达式：1+(2+3)4-5 前缀表达式：-+1 +2 3 4 5 后缀表达式：1 2 3+4 +5-一、中缀表达式 中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。二、前缀表达式 前缀表达式的运算符位于两个相应操作数之前，前缀表达式又被称为前缀记法或波兰式 前缀表达式的计算机求值。1.从右至左扫描表达式 2.遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈 3.重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果 示例：计算前缀表达式的值：-+1 +2 3 4 5 1.从右至左扫描，将 5，4，3，2 压入堆栈；2）遇到+运算符，弹出 2 和 3（2 为栈顶元素，3 为次顶元素），计算 2+3 的值，得到 5，将5 压入栈；3）遇到运算符，弹出 5 和 4，计算 54 的值，得到 20，将 20 压入栈；4）遇到 1，将 1 压入栈；5）遇到+运算符，弹出 1 和 20，计算 1+20 的值，得到 21，将 21 压入栈；6）遇到-运算符，弹出 21 和 5，计算 21-5 的值，得到 16 为最终结果 可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配 三、后缀表达式 后缀表达式与前缀表达式类似，只是运算符位于两个相应操作数之后，后缀表达式也被称为后缀记法或逆波兰式。后缀表达式的计算机求值 与前缀表达式类似，只是顺序是从左至右：1.从左至右扫描表达式 2.遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈 3.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 示例：计算 计算后缀表达式的值：1 2 3+4 +5-1）从左至右扫描，将 1，2，3 压入栈；2）遇到+运算符，3 和 2 弹出，计算 2+3 的值，得到 5，将 5 压入栈；3）遇到 4，将 4 压入栈 4）遇到运算符，弹出 4 和 5，计算 54 的值，得到 20，将 20 压入栈；5）遇到+运算符，弹出 20 和 1，计算 1+20 的值，得到 21，将 21 压入栈；6）遇到 5，将 5 压入栈；7）遇到-运算符，弹出 5 和 21，计算 21-5 的值，得到 16 为最终结果 四、中缀表达式转化为前缀和后缀表达式 转化步骤：1.按照运算符的优先级对所有的运算单位加括号 2.将运算符移动到对应括号的前面（前缀表达式）或后面（后缀表达式）3.去掉括号，得到前缀或后缀表达式 示例：中缀表达式：1+(2+3)4-5 1）加括号 式子变成(1+(2+3)4)-5)2）移动运算符 对于前缀表达式，变成了-(+(1(+(23)4)5)对于后缀表达式：变成了(1(23)+4)+5)-3）去掉括号 前缀表达式：-+1 +2 3 4 5 后缀表达式：1 2 3+4 +5-五、小结 前缀、中缀、后缀是根据运算符与操作数的相对位置来划分的 中缀表达式符合人的计算习惯，而前缀和后缀表达式适合计算机计算 前缀表达式和后缀表达式计算的时候都是从一个方向扫描表达式，遇到数字压入栈，遇到运算符弹出栈顶的两个数进行运算并将结果入栈，重复知道结束 前缀和后缀表达式已经内在地包含运算顺序，因此不用括号来确定优先级