表达式的逆波兰表示

      后缀表达式又叫逆波兰表达式。那么如何讲中缀表达式转化为后缀表达式呢？
      比如已知中缀表达式a+b*c+(d*e+f)*g，如何将其转化为后缀表达式abc*+de*f+g*+呢？有4个基本原则。

      1. 当读到操作数时，立即输出（由后缀表达式的形式明显可以看出，操作数的输出优先级要比操作符要高）；当读到操作符时，并不立即输出，而是将其存于堆栈中。
      2. 如果见到右括号，那么将栈元素弹出，直到遇到左括号。但是左括号只是弹出，并不输出。
      3. 如果见到其他符号，我们将栈中输出优先级更高（或者相同）的符号全部弹出。然后将此符号入栈。（即把别人挤出去之后，自己入栈）
      4. 强调一下，比如见到符号“+”，如果栈顶有符号“-”。优先级相同。需要将“-”弹出，“+”入栈。优先级相同也要弹出！

      下面举个例子，写出a+b*c+(d*e+f)*g的后缀表达式。

     （画图表示不方便，我们用下表表示转换过程）

 

  
     

 

备注1：
      首先读到a，因为a属于操作数，直接输出

备注2：
      读到“*”号。栈顶符号“+”号的优先级不比“*”号的优先级高，也不是不相同。故将“*”入栈。

备注3：
      读“+”号，因为栈顶符号“*”比读到的“+”优先级高，栈顶符号“+”与独到的“+”优先级相同，故“*”和“+”都弹出。将刚读到的“+”号入栈。

备注4：
      读到“（”，将“）“后的栈顶元素全部输出。

备注5：
      输入串遍历完毕，将栈中剩余元素全部弹出。