## Concept:

# Reverse_Polish_notation

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

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

## Metadata

### There are no revisions for this page.

## User contributions

## 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.
**

#### 10 most similar pages:

- Concept:Transcompiler - 0.3774502
- Concept:Recursion removal - 0.3559031
- Concept:Fold_function - 0.353019
- Concept:Rose tree - 0.34712902
- Technology:GeFLo - 0.29016563
- Concept:Fibonacci number - 0.26314747
- Issue:NotFound - 0.26170927
- Concept:Tuple type - 0.2555196
- Concept:Factorial - 0.2549697
- Concept:NotFound - 0.25477237

## 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.
**