Reverse Polish Notation

  • Created by: 043481
  • Created on: 02-05-14 09:12
View mindmap
  • 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.
    • What are the advantages?
      • Brackets are not needed.
      • They can be solved using stacks.
      • Binary trees are important, as reverse polish notation can be gained.
      • Important in Computing as expressions written in it are unambiguous.


No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Reverse Polish Notation resources »