Penny.Liberty.Expressions.RPN

Parses reverse polish notation expressions. This module needs much better error messages (right now it has none).

An RPN expression consists of operands and operators; a token is either an operand or an operator. For example, in the expression 5 4 +, the 5 and the 4 are operands; the + is an operator; each of these three is a token.

Documentation

newtype Operand a

An operand; for example, in the expression 5 4 +, 5 and 4 are operands.

Constructors

Operand

Fields

unOperand :: a

Instances

Show a => Show (Operand a)

data Operator a

Operators; for example, in the expression 5 4 +, + is an operator. Because this is RPN, there is no operator precedence.

Constructors

Unary (a -> a)

Unary operators take only one operand (for example, a factorial operator).

Binary (a -> a -> a)

Binary operators take two operands (for example, an addition operator).

Instances

Show (Operator a)

data Token a

A token is either an operator or an operand.

Constructors

TokOperand (Operand a)

TokOperator (Operator a)

Instances

Show a => Show (Token a)

process

Arguments

:: Foldable l

=> l (Token a)

The tokens must be in the sequence from left to right in postfix order; for example, 5 4 - will yield 1. Typically many appends will be required in order to build this sequence. If performance is a concern, you can use a Data.Sequence; if the list is small (as these lists will typically be) a regular list will do just fine.

-> Maybe a

Fails if there is not exactly one operand remaining on the stack at the end of the parse, or if at any time there are insufficient operands on the stack to parse an operator. Otherwise, succeeds and returns the result.

Processes an entire input sequence of RPN tokens.