Translation to and from Polish notation

[SlideRule]

An excerpt from Translation to and from Polish Notation {C. L. Hamblin}

"Reverse Polish notation is embodied in the instruction languages of two recent machines, and Forward Polish notation is of use in mechanized algebra. This article illustrates, using a simple language without detail, some methods of translating between these notations and an 'orthodox' one of the kind used in FORTRAN and ALGOL.
…
… The following cases of translation will be considered in detail:
I. Orthodox A to Reverse Polish.
II. Orthodox A to Forward Polish.
III. Forward Polish to Orthodox A.
IV. Forward Polish to Reverse Polish.
These cases provide a survey of the relevant techniques …"

BEST!
SlideRule

[KeithB]

This is essentially what yacc does. It takes a c expression in algebraic notation and turns it into a RPN stream.

[toml_12953]

(11-15-2019 04:54 PM)SlideRule Wrote:  An excerpt from Translation to and from Polish Notation {C. L. Hamblin}

"Reverse Polish notation is embodied in the instruction languages of two recent machines, and Forward Polish notation is of use in mechanized algebra. This article illustrates, using a simple language without detail, some methods of translating between these notations and an 'orthodox' one of the kind used in FORTRAN and ALGOL.
…
… The following cases of translation will be considered in detail:
I. Orthodox A to Reverse Polish.
II. Orthodox A to Forward Polish.
III. Forward Polish to Orthodox A.
IV. Forward Polish to Reverse Polish.
These cases provide a survey of the relevant techniques …"

BEST!
SlideRule

Here's an ANSI BASIC program that interprets a postfix string:

Code:

DECLARE EXTERNAL SUB rpn
PUBLIC NUMERIC R(64)                             ! stack
PUBLIC STRING expn$                              ! for keyboard input
PUBLIC NUMERIC i, lenn, n, true, false           ! global values
LET true = -1
LET false = 0

DO
   PRINT "enter an RPN expression:"
   INPUT expn$
   IF LEN( expn$ ) = 0 THEN EXIT DO 
   PRINT "expn: ";expn$      
   CALL rpn( expn$ )
LOOP

END

! interpret reverse polish (postfix) expression
EXTERNAL SUB rpn( expn$ )
DECLARE EXTERNAL FUNCTION is_digit, get_number
DECLARE STRING ch$
 
LET expn$ = expn$ & " "                          ! must terminate line with space
LET lenn = LEN( expn$ )

LET i = 0
LET n = 1
LET R(n) = 0.0                                   ! push zero for unary operations

DO

   IF i >= lenn THEN EXIT DO                     ! at end of line
   LET i = i + 1
    
   IF expn$(i:i) <> " " THEN                     ! skip white spaces
    
      IF is_digit( expn$(i:i) ) = true THEN      ! push number onto stack
         LET n = n + 1
         LET R(n) = get_number
      ELSEIF expn$(i:i) = "+" then               ! add and pop stack
         IF n < 2 THEN
            PRINT "stack underflow"
         ELSE
            LET R(n-1) = R(n-1) + R(n)
            LET n = n - 1
         END IF
      ELSEIF expn$(i:i) = "-" then               ! subtract and pop stack
         IF n < 2 THEN
            PRINT "stack underflow"
         ELSE
            LET R(n-1) = R(n-1) - R(n)
            LET n = n - 1
         END IF
      ELSEIF expn$(i:i) = "*" then               ! multiply and pop stack
         IF n < 2 THEN
            PRINT "stack underflow"
         ELSE
            LET R(n-1) = R(n-1) * R(n)
            LET n = n - 1
         END IF
      ELSEIF expn$(i:i) = "/" THEN               ! divide and pop stack
         IF n < 2 THEN
            PRINT "stack underflow"
         ELSE
            LET R(n-1) = R(n-1) / R(n)
            LET n = n - 1
         END IF
      ELSEIF expn$(i:i) = "^" THEN               ! raise to power and pop stack
         IF n < 2 THEN
            PRINT "stack underflow"
         ELSE
            LET R(n-1) = R(n-1) ^ R(n)
            LET n = n - 1
         END IF
      ELSE
         PRINT REPEAT$( " ", i+5 ); "^ error"
         EXIT DO 
      END IF
   END IF
LOOP

PRINT "result: "; R(n)                           ! end of main program

END SUB

! extract a number from a string
EXTERNAL FUNCTION get_number
DECLARE EXTERNAL FUNCTION is_digit
LET j = 1                                        ! start of number string
DECLARE STRING number$                           ! buffer for conversion

DO                                               ! get integer part
   LET number$(j:j) = expn$(i:i)
   LET i = i + 1
   LET j = j + 1
   IF is_digit( expn$(i:i) ) = false THEN
      IF expn$(i:i) = "." then          
         LET number$(j:j) = expn$(i:i)           ! include decimal point
         LET i = i + 1
         LET j = j + 1
         DO WHILE is_digit( expn$(i:i) ) = true  ! get fractional part
            LET number$(j:j) = expn$(i:i)
            LET i = i + 1
            LET j = j + 1
         LOOP
      END IF
      EXIT DO
   END IF
LOOP

LET get_number = VAL( number$ )

END FUNCTION

! check for digit character
EXTERNAL FUNCTION is_digit( ch$ )

IF "0" <= expn$(i:i) AND expn$(i:i) <= "9" THEN
   LET is_digit = true
ELSE
   LET is_digit = false
END IF
END FUNCTION