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