Reverse Polish Notation

HideShow resource information
• Created by: 043481
• Created on: 02-05-14 09:12
• Reverse Polish Notation
• Method of writing mathematical expressions without brackets.
• This done by placing the operator after the operand.
• Also known as post-fix noation
• Adding two numbers is written as A+B, this is infix notation.
• To multiply the result by two, we'd write 2*(A+B)
• In reverse polish notation this would be AB+2*
• In reverse polish notation this would be AB+
• Binary trees can be used to convert between the different notations.
• Using in-order  traversal will result in normal, infix notation.
• Post order traversal is used to get reverse polish notation.
• By highlighting each major part of an expression, in the order it is calculated, a binary tree can be made.
• Stacks can be used to evaluate expressions.
• 1. Read expression from left to right.
• 2. If a number is encountered, push onto the stack.
• 3. If an operator is encountered, pop two numbers from the stack and carry out the operation.
• 4. Push the result of the operation on to the stack.
• 5. End if last item in the expression.