# Suffix expression to infix expression

2020-11-08 18:11:44

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