Suppose there is a suffix expression 1 2 3 + 4 * +5 – , Please convert it to a prefix expression .
Using expression tree ：
1. Scan the suffix expression from left to right , One symbol at a time reads into the expression .
2. If the symbol is an operand , Then create a single node tree and push it onto the stack . If the sign is an operator , Then pop up two trees from the stack T1 and T2（T1 First pop up ） And form a new tree , The root of the tree is the operator ,
Its left 、 The right sons are T2 and T1( The first one is the right subtree , The last one is left subtree ). Then push the pointer to the new tree onto the stack .
The first three symbols are operands , So create three single node trees and push pointers to them onto the stack
“+” Be read into , So the pointer to the last two trees pops up , Form a new tree , And push the pointer to the new tree onto the stack .
scanning 4 and * after
scanning + and 5 after
scanning - after
