您好、欢迎来到现金彩票网!
当前位置:众彩 > 分枝法 >

士说新语 逆掀起波兰抛弃了我~~逆波兰式到底是怎么来的

发布时间:2019-05-27 14:08 来源:未知 编辑:admin

  对于这道题的算法,很多同学都选择了直接背下来,更有同学好奇这样一种算法是怎么发明出来的。其实,对于这种算法,我们有着一种通俗的理解方法。

  但是,为了让同学们更好地理解这种算法,我们先静下心来分析一下,我们通常所说的“计算算式”到底是怎样一个流程。我们不妨以A+B*(C-D)-E*F为例。

  这道题的计算过程显而易见。先将C与D作差,将B与其结果相乘,将A与该结果相加,将E与F相乘,再将两结果作差。画成流程图大概就是这样一个过程。

  但是对于计算机来说,这个过程就显得有些困难了。因为没有一种简单的数据结构可以高效地从一个表达式中间抽出一部分(如上式中的C-D),算完结果,再放回原来的位置,然后继续进行正常计算(链表可以实现,但复杂度代价过大)。所以,为了提高计算机的计算效率,我们需要另辟蹊径。

  现在回到上面这张流程图来。将其上下翻转,我们就得到了一种经典的数据结构——二叉树。

  和其他的二叉树不同的是,我们的这棵二叉树只有叶节点才有操作数。我们只有计算出了下层的结果,才可以获得上层操作符所对应的操作数。因此,这里可以采用分治的思想,先计算出一个操作符左右子树的操作数,再按操作符进行计算。具体实现顺序有以下三种:

  显而易见的是,无论是前序遍历还是后序遍历,一个运算符的被读取顺序和其执行顺序都是一致的(前序遍历是先读后算,后序遍历是先读先算),而中序遍历可能出现读取顺序和运算顺序不一致的情况。

  如C*(A-D+B),运算符的实际运算顺序是 - + * ,前序遍历读取顺序是 * + - ,后序遍历读取顺序是 - + * ,中序遍历读取顺序却是 * - + ,这也是中序表达式需要括号来标定优先级的原因。

  因此,前缀、后缀表达式只需要进行一次遍历便可完成运算,对计算机运算来说极大地减少了时间复杂度。

  当然一提到分治法,很多同学的脑中自然就出现了递归的实现方法。然而,人类在漫长的实践过程中发现,在一个函数调用之前需要做许多工作,比如准备函数内局部变量使用的空间、搞定函数的参数等等,这些事情每次调用函数都需要做,因此会产生额外开销导致递归效率偏低。为了追求更高的计算效率,唯有突破界限。

  利用递归函数的原理,我们可以用更加底层的栈运算来模拟递归函数执行。因而,我们才获得了波兰式法(对应二叉树的前序遍历)和逆波兰法(对应二叉树的后序遍历)。其原理就是将中序表达式当作一棵二叉树,先进行前序/后序读取,再进行计算。

  🔷 若是运算符(+,-,*,/),则从栈中弹出两个元素进行计算(注意:后弹出的是左运算数),并将计算结果进栈。

  🔷 遍历结束,将计算结果从栈中弹出(栈中应只有一个元素,否则表达式有错)。

  当然,如果题目中不需要输出后缀表达式的话,我们还可以将构造后缀表达式过程中的某些步骤省略掉,转为直接进行计算,从而进一步优化算法。具体实现方法就留给大家自己思考了。

  当然,同学们下次遇到手动转换后缀表达式的题目的时候,也可以尝试一下先构造运算二叉树,再模拟后序遍历得到结果哦。当然,如果同学们有什么问题或见解的话,也欢迎在留言区进行讨论。

http://jigsawesl.com/fenzhifa/330.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有