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.
A Haskell-based implementation of the algorithm follows.

This is the syntax that we use:

-- 5 1 2 + 4 * + 3 -
sample :: RPN
sample = [
             Operand 5,
             Operand 1,
             Operand 2,
             Operator Plus,
             Operand 4,
             Operator Times,
             Operator Plus,
             Operand 3,
             Operator Minus
         ]

-- 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

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

Here is a simple evaluator which process operands and operators one by one:

-- Evaluation of RPN via stack
eval :: RPN -> Int
eval = loop empty
  where
    -- Loop over input
    loop :: Stack Int -> 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 Int -> Stack Int
    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     

-- Reusable error
rpnError :: a
rpnError = error "RPN corrupted"

Ralf Lämmel edited this article at Sat, 04 Jun 2022 11:13:31 +0200
Compare revisions Compare revisions

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.