Want to build a tree with an expression that is given in
infix notation? Here are the rules:
Keep track of what node you are in in your tree. This means nodes are going to have to have a parent element.
- ( - insert a '(', then go downleft one node. Do not include this when you go back for reading the RPN expression.
- ) - recurse up the tree until the node you are on is a '('.
- +, -, *, / - recurse up until you are at a node who's parent is an operator of higher precedence, then move the node at the current location down and to the left (without chaning the current location), insert the operator at current location, then move the current location down and to the right.
- A number - insert at current location.
To get out the RPN expression, just read the tree in postorder.
Precedence table (a.k.a. order of operations):
- Parentheses
- Multiplication and division (read left to right)
- Addition and subtraction (read left to right)
If you add modulus (%), put that in with multiplication and division. If you add exponents (^), put it between parentheses and multiplication/divison.