首页 > 代码库 > 前缀表达式求解

前缀表达式求解

问题描述:

  前缀表达式也叫波兰表达式,是将操作符前置的一种写法。

  中缀到前缀示例:

    ( 4 + 2 ) * ( 3 + 6 ) =>  * + 4 2 + 3 6

    (3 + 4 / 2) - 5 => - + 3 / 4 2 5

 

思路1(递归):

  1. 从左向右扫描

  2. 因为前缀表达式里都是双目运算符,且没有括号,所以遇到操作符可以递归求解,例如遇到乘号:

    case ‘*‘:

      return exp() * exp();

 

思路2(栈):

  1. 维护数字栈

  2. 从右向左扫描,遇到数字则入栈,遇到符号则出栈两个数字,计算后再入栈新数字,前缀表达式与后缀表达式求法对称,所以直接按后缀法相反方向求解即可。

 

 

转载请注明引用自:

  http://www.cnblogs.com/breakthings/p/4051773.html 

前缀表达式求解