Headline

A mathematical notation where operators follow their operands

Illustration

Consider the following expression using regular infix operators:

5 + ((1 + 2) * 4)  3

In RPN:

5 1 2 + 4 * + 3 -

RPN can be evaluated by means of a simple iterative, stack-based algorithm which handles one input item (operator or operand) in each iteration. An operand is pushed on the stack. An operator is immediately applied to the two top-most stack entries. When the (well-formed) input has been consumed, then the result of expression evaluation is the one and only entry on the stack.

The input "5 1 2 + 4 * + 3 -" is processed as follows:

  • Push 5 on the stack.
  • Push 1 on the stack.
  • Push 2 on the stack.
  • Apply "+" to second top of stack (1) and top of stack (2); pop twice, push 3.
  • Push 4 on the stack.
  • Apply "*" to second top of stack (3) and top of stack (4); pop twice, push 12.
  • Apply "*" to second top of stack (5) and top of stack (12); pop twice, push 17.
  • Push 3 on the stack.
  • Apply "-" to second top of stack (17) and top of stack (3); pop twice, push 14.
See
module RPN where

import Stack

-- RPN as lists of operators and operands
type RPN = [Entry]
data Entry = Operator Operator | Operand Operand
  deriving (Show)
data Operator = Plus | Minus | Times
  deriving (Show)
type Operand = Int

-- Evaluation of RPN via stack
eval :: RPN -> Int
eval = loop empty
  where
    -- Loop over input
    loop :: Stack -> RPN -> Int
    loop s i =
      if null i
        then if size s == 1
               then top s
               else rpnError
        else
          loop (step (head i) s) (tail i)

    -- Process head of input
    step :: Entry -> Stack -> Stack
    step h s =
      case h of
        Operand x -> push x s
        Operator f -> 
          if size s >= 2
            then 
              let (x,s') = (top s, pop s) in
              let (y,s'') = (top s', pop s') in
              push (apply f y x) s''
           else rpnError     

-- Interpretation of operator symbols
apply :: Operator -> Int -> Int -> Int
apply Plus = (+)
apply Minus = (-)
apply Times = (*)

-- Reusable error
rpnError :: a
rpnError = error "RPN corrupted"
for a Haskell-based implementation of the algorithm.

Metadata



There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.