infix-prefix: a library to convert prefix expressions to infix and vice versa

8.12

infix-prefix: a library to convert prefix expressions to infix and vice versa🔗ℹ

Ruslan Popov

(require infix-prefix)

package: infix-prefix

1 Warnings🔗ℹ

It is not heavily tested.
Infix to prefix functionality does not count proper precedence and associativity.
I’m not sure if unary operators are parsed correctly.

2 Prefix to infix🔗ℹ

In order to convert a prefix expressions to infix you need to create a table of operators (by make-ops-table).

Then you should call the prefix->infix function with an expression to parse and your operators table. From the library, a default operators table is available for addition, subtraction, multiplication and division.

Example:

#lang racket

(require infix-prefix)

(define my-ops
(make-ops-table
[+ 1 left-right]
[- 1 left]
[* 2 left-right]
[/ 2 left]))

(println (prefix->infix '(+ x y (* z w)) my-ops)) ; '(x + y + z * w)

Inner implementation:

Firstly, expression is converted to a binary tree. That means all forms like (+ 1 2 3) is converted to (+ 1 (+ 2 3)). WARNING: There is a bug, this works correctly for left associative expressions only.
Then, binary expression are convert to prefix form. This form does not count associativity and precedence, instead it wraps all in parenthesis.
Finally, groupings are removed according to operators table were they are unnecessary.

3 Infix to prefix🔗ℹ

In order to convert an infix expression to prefix you need to define a special parser with define-infix->prefix-parser. You should supply name and operators that you need to parse.

Then you can call that parser by name and supply an expression.

Example:

#lang racket

(require infix-prefix)

(define-infix->prefix-parser my-parser
+ - * /)

(println (my-parser '(x + y * z))) ; '(+ x (* y z))

Inner implementation:

The define-infix->prefix-parser form uses match. It searches for operators inside an expression, splits expression into left and right part, and then calls itself recursively and makes a prefix expression.

4 Functions🔗ℹ

procedure
(prefix->infix expr ops) → any/c
expr : any/c
ops : hash?

Converts a prefix expression into infix form by operators table. The operators table must be created via make-ops-table form.

syntax
(make-ops-table clause ...)

clause = (operator precedence associativity)

   operator : symbol?
   precedence : integer?
   associativity : (or/c 'left 'right 'left-right)

Create an operators table. For more details refer to the provided grammar of clause.

syntax
(define-infix->prefix-parser name op ...)

name : symbol?
op : symbol?

Define an infix to prefix parser with name name. The precedence of operators is encoded in the order of op.