根据算数表达式(中缀式)求波兰表达式和逆波兰表达式

一共有两种求法,直接举例。
y+(2-3*y+4)*((4+y)*2-y) 的波兰表达式和逆波兰表达式。

第一种方法——直接画出二叉树

直接画出二叉树根据前序和后序遍历求得波兰表达式和逆波兰表达式。
中缀式的二叉树

波兰表达式: +y*+-2*3y4-*+4y2y
逆波兰表达式: y23y*-4+4y+2*y-*+

第二种方法——括号替换法

求波兰表达式:

  1. 将中缀式的括号补全(保证一对括号里有且仅有一个直接的运算符)
    (y+(((2-(3*y))+4)*(((4+y)*2)-y)))
  2. 将这一对括号中的运算符把前括号( 替换,忽略后括号)。
    +y*+-2*3y4-*+4y2y

求逆波兰表达式:

  1. 将中缀式的括号补全(保证一对括号里有且仅有一个直接的运算符)
    (y+(((2-(3*y))+4)*(((4+y)*2)-y)))
  2. 将这一对括号中的运算符把后括号( 替换,忽略前括号)。
    y23y*-4+4y+2*y-*+