Infixed to postfixed notation converter
published: 15 June 2020 / updated 15 June 2020
Prefixed, infixed and postfixed notations
The FORTH language uses a so-called postfixed notation also called notation RPN. The notation RPN allows you to do without the parentheses used in infix notation:
- infixed notation:
( 2 + 3 ) * 2 - postfixed notation:
2 3 + 2 *
The notation known as prefixed is used by certain languages, such as LISP:
- prefixed notation:
(* 2 (+ 2 3 ) )
For FORTH, the problem is to find a reliable method to convert formulas classical arithmetic, called infixed, in postfixed notation exploitable by FORTH.
From this problem was born the idea of creating a program - in FORTH - to perform this conversion.
The infixed to postfixed conversion program
The initial program was developed to work with TURBO-Forth under MS-DOS.
Original version:
CREATE OP 44 ALLOT
: ?INTERP ( PFA ---) STATE @ IF , ELSE EXECUTE THEN ;
: OPP@ ( --- ADR) OP DUP @ + ;
: >OP ( PFA NIVEAU ---) 4 OP +! OPP@ 2! ;
: OP> ( ---) OPP@ 2@ -4 OP +! DROP ?INTERP ;
: LEV? ( --- NIVEAU) OPP@ @ ;
: ]$ BEGIN LEV? WHILE OP> REPEAT FORTH ; IMMEDIATE
: TRAITE ( PFA --- ) 2@
BEGIN DUP LEV? > NOT
WHILE >R >R OP> R> R> REPEAT >OP ;
: INFIX ( N --- <MOT> <MOT> EN COMPILATION )
' CREATE SWAP , , IMMEDIATE
DOES> TRAITE ;
VOCABULARY ALGEBRE ALGEBRE DEFINITIONS
7 INFIX * * 7 INFIX / / 6 INFIX + + 6 INFIX - -
5 INFIX > > 5 INFIX < < 5 INFIX = =
4 INFIX NOT NOT 3 INFIX AND AND 2 INFIX OR OR
: ( ['] CR 1 >OP ; IMMEDIATE
: ) [ FORTH ] BEGIN 1 LEV? < WHILE OP> REPEAT
1 LEV? = IF -4 OP +! ELSE TRUE ABORT" MANQUE (" THEN ;
IMMEDIATE
FORTH DEFINITIONS
: $[ OP 44 0 FILL ALGEBRE ; IMMEDIATE This version was written in 1987.
The current version has been rewritten and adapted to be compiled by gForth.
The operator stack
In order to manage the priority in the execution order of the infix operators and the
parentheses nesting, it is necessary to manage these operators in a stack
named op:
80 constant OPERATORS \ increase value 80 if needed cell 2* OPERATORS * constant OP-SIZE create op \ operator stack OP-SIZE allot \ get current operator pointer : opp@ ( --- addr ) op dup @ + ; \ increase operator pointer : opp+ ( ---) cell 2* op +! ; \ decrease operator pointer : opp- ( ---) cell 2* negate op +! ; : ?interp ( cfa ---) state @ \ 0 = interpret mode, -1 = compile mode if compile, \ compile word else execute \ execute word then ; : >op ( pfa level ---) opp+ opp@ 2! ; : op> ( ---) opp@ 2@ opp- drop ?interp ;
gForth being a 32-bit stack system, we adapted the stack size
op in this 32-bit integer format.
The stack pointer is stored in the first cell of this
op stack. The pointer is incremented by opp+
and decremented by opp-.
The word opp@ returns the real address in the op stack.
pointed to by the stack pointer.
The word >op increments the stack pointer op
and stores the operator to put on hold and its level.
The word op> retrieves the operator on hold and its level.
The stack pointer op is then decremented and
the operator is executed or compiled.
Definition of the infix operators
\ get level pointed by current operator stack : lev? ( --- level) opp@ @ ; : ]$ begin lev? while op> repeat forth ; immediate : dealing ( pfa --- ) 2@ begin dup lev? > invert while >r >r op> r> r> repeat >op ; : infix ( n --- <word1> <word2> in compilation ) ' \ get cfa word1 create \ create word2 swap , , immediate does> dealing ; vocabulary algebra algebra definitions 7 infix * * 7 infix / / 6 infix + + 6 infix - - 5 infix > > 5 infix < < 5 infix = = 4 infix invert not 3 infix and and 2 infix or or
The word ]$ closes an infixed arithmetic sequence. This word
loop until the op stack is empty.
The word infix is a definition word used to create
operators infixed in the vocabulary algebra. Syntax of
definition of an infix operator: n infix <word1> <word2>:
- n is the operator level
- <word1> is the word to execute when the infix formula is executed or compiled
- <word2> is the word to create in the vocabulary
algebra
Définition des parenthèses
: ( ['] cr 1 >op ; immediate : ) [ forth ] begin 1 lev? < while op> repeat 1 lev? = if opp- else true abort" miss " 40 emit then ; immediate
The words ( and ) are also compiled in the vocabulary
algebra. The word ( in the vocabulary algebra
works as a level 1 operator. Compiling the word cr
is simply used to store a neutral word which will not be executed.
The word ) in the vocabulary algebra deals with the formula section
marked with (. Example: $[ ( 2 + 3 ) ]$
Opening an infixed arithmetic sequence
forth definitions : $[ op OP-SIZE 0 fill algebra ; immediate
The word $[ opens an infixed arithmetic sequence which
ends with the word ]$.
Example:
: ex1 ( --- n)
$[ ( ( 2 + 3 ) * ( 4 + 1 ) ) ]$
\ two 3 + 4 1 + *
;
Practical use
The full code is available here: infix.txt
It must be compiled with gForth.
Once compiled, test the example ex1:
: ex1 ( --- n) compiled $[ ( ( 2 + 3 ) * ( 4 + 1 ) ) ]$ compiled ; ok ok see ex1 : ex1 2 3 + 4 1 + * ; ok
The sequence see ex1 allows us to decompile our example ex1 .
In this decompilation, we see that our algebraic expression
( ( 2 + 3 ) * ( 4 + 1 ) )
has become
2 3 + 4 1 + *
Using variables
In an infixed expression, we can use variables of type values. Example:
0 value X 0 value A 0 value B 0 value C : toABCX ( a b c x ---) to X to C to B to A ; : ex2 ( --- n) $[ ( A * ( X * X ) ) + ( B * X ) + C ]$ ;
Decompiling ex2 gives A X X * * B X * + C +.
Use:
1 1 1 2 toABCX ok ex2 ok .s <1> 7 ok
Logical expressions
We can also deal with logical expressions:
: toABC ( a b c ---) to X to C to B to A ; : ex3 ( --- fl ) $[ ( not A and C ) or ( B and not C ) or ( A and not B ) ]$ ;
The decompilation of ex3 give A invert C and B C invert and or A B invert and or
Here is an example that mixes arithmetic and logical expressions. This example proposes to convert a temperature from degrees Celsius to degrees Kelvin or Fahrenheit:
0 value KELVIN 0 value FAHRENHEIT 0 value tempCelsius : toK ( ---) false to FAHRENHEIT true to KELVIN ; : toF ( ---) false to KELVIN true to FAHRENHEIT ; : C. ( deg --- deg2) to tempCelsius $[ ( ( tempCelsius + 273 ) and KELVIN ) + ( ( ( tempCelsius * 9 / 5 ) + 32 ) and FAHRENHEIT ) ]$ . \ display result ;
In this sequence ( tempCelsius + 273 ) and KELVIN we convert
degrees Celsius in degrees Kelvin. The variable KELVIN contains
a boolean flag: if it is zero, the result of the conversion will be zero. In the case
otherwise the result will correspond to the calculation. The process is the same on the next line,
where we do a logical and with the result in degrees Fahrenheit.
Example of use:
10 ToF C. 42 ok 10 toK C. 283 ok
Here is the result of the decompilation of our formula in C.:
tempCelsius 273 + KELVIN and tempCelsius 9 * 5 / 32 + FAHRENHEIT and +
If we want to reuse this portion of decompiled code on FlashForth, we can write our code like this:
0 value KELVIN 0 value FAHRENHEIT 0 value tempCelsius : toK ( ---) false to FAHRENHEIT true to KELVIN ; : toF ( ---) false to KELVIN true to FAHRENHEIT ; : C. ( deg --- deg2) to tempCelsius tempCelsius 273 + KELVIN and tempCelsius 9 * 5 / 32 + FAHRENHEIT and + . \ display result ;
Conclusion
Converting infixed arithmetic expressions to postfixed expressions allows convert error-free complex arithmetic or logical expressions.
With gForth, we will compile infixed expressions, then recover the decompilation of these expressions, we can use them on other versions of Forth, in particular on FlashForth which does not integrate the notion of vocabulary from the outset.
gForth integrates real numbers (floating point). It is therefore possible to create a variant of these routines to deal with real numbers. If you realize this variant, contact me for a possible publication.