QL stack calculator

[tcat]

Hi,

Just trying to follow Peter-Sulzer's post on stack calculations, and `EJC'.
Learning from the Wiki, we have so called `infix' and `postfix' notations. The latter sometimes called `reversed Polish' e.g. found implemented on HP calculators, also the idea of `FORTH' programming language.

Infix formula as we know from normal maths.

Code: Select all

5 * ( 6 + 2 ) - 12 / 4

Equivalent postfix formula, that reversed Polish.

Code: Select all

5 6 2 + * 12 4 / -

EDIT, a typo
As Postfix is easy to evaluate, using Push(), Pop(), the idea is to convert Infix formula into Postfix first.

Infix-To-Postfix notation conversion pseudo code

Code: Select all

Start with an empty stack.
We scan Infix expression `Q' from left to right, and we produce `P' postfix formula from it.

While (we have not reached the end of Q)
  If (an operand is found)
    Add it to P
  End-If

  If (a left parenthesis is found)
    Push it onto the stack
  End-If

  If (a right parenthesis is found)
    While (the stack is not empty AND the top item is not a left parenthesis)
      Pop the stack and add the popped value to P
    End-While
    Pop the left parenthesis from the stack and discard it
  End-If

  If (an operator is found)
    If (the stack is empty or if the top element is a left parenthesis)
      Push the operator onto the stack
    Else
      While (the stack is not empty AND the top of the stack 
                is not a left parenthesis AND precedence of the
                operator <= precedence of the top of the stack)
        Pop the stack and add the top value to P
      End-While
      Push the latest operator onto the stack
    End-If
  End-If

End-While

While (the stack is not empty)
  Pop the stack and add the popped value to P
End-While

NOTE, just copied from university IT seminar, assuming it may be right

It would be interesting to know, how this is handled by QL arithmetic stack, as Super BASIC interpreter must do something similar for us?

TODO postfix formula evaluation is easier, I will copy in the next post.

Tomas

[tcat]

Hi ql_freak,

I have filed this thread, as I wanted to share your interest in `EJC', `PDQL-C' and the like.

As I have always wondered how expression evaluation works, `FORTRAN' probably first among languages getting that right and earning a huge fortune to IBM.

I hope no offense.

Cheers
Tomas

[tcat]

Hi,

Here I copy `Postfix' expression evaluator pseudo code, again taken from an university seminar, found on the web.

Code: Select all

We start with an empty stack. We scan `P' postfix formula from left to right.

While (we have not reached the end of P)
  If an operand is found
    push it onto the stack
  End-If

  If an operator is found
    Pop the stack and call the value A
    Pop the stack and call the value B
    Evaluate B op A using the operator just found.
    Push the resulting value onto the stack 
  End-If

End-While
Pop the stack (this is the final value)

Tomas

[pjw]

My interest in programming started with an HP41CX RPN calculator. What a wonderful machine that was! When I bought my first QL, writing an HP41 emulator was one of my earliest programming ambitions. I wanted something that would store and run my many hand-scribbled HP41 programs (a 4k memory pack for the HP41 cost over $100!), but I got stuck trying to develop a compatible floating point format. It was way beyond my knowledge and technical skill at the time, and information was hard to come by up here in the then digitally challenged North. I sketched a few RPN calculators using QL fp, but they are unfinished and mainly rubbish. Once the Internet arrived, quite a few nice HP41 emulators appeared for mainstream computers.

Laurence Reeves, of Minerva fame, has written a very competent RPN calulator, ECalc, for the PC, but it isnt HP41-like, nor even programmable. Cant find it on the Web any more. Someone called Peter Lauridsen wrote a "Scientific Reverse Polish Notation Calculator" for the QL. I think its just called RPN_obj. It comes with source code. I dont know if its available for download anywhere, but I have a copy if anyone wants it to look at.

[tcat]

Hi Per,

I am glad my post raised some interest at last. Very interesting story of yours with HP. I was challenged by ql_freak's below expression.

Code: Select all

(8+3*4+7)^(1/3)

Postix equivalent

Code: Select all

8 3 4* 7++ 1 3/^

Here is possibly buggy, but simplified postfix evaluator, but carries the idea

Code: Select all

100 DEFine PROCedure calc (expr$)
110 LOCal op$,v
120 DIM st(10)
130 op$=''
140 FOR i=1 TO LEN(expr$)
150  IF expr$(i) INSTR "0123456789."  THEN op$=op$&expr$(i): NEXT i
160  IF expr$(i) INSTR "pi"           THEN op$=op$&expr$(i): NEXT i
170  IF expr$(i) INSTR "sincosloglne" THEN op$=op$&expr$(i): NEXT i
180  IF op$=="PI"  THEN push PI          : op$=''
190  IF op$=="SIN" THEN push (SIN(pop))  : op$=''
200  IF op$=="COS" THEN push (COS(pop))  : op$=''
210  IF op$=="LOG" THEN push (LOG10(pop)): op$=''
220  IF op$=="LN"  THEN push (LN(pop))   : op$=''
230  IF op$=="E"   THEN push (EXP(pop))  : op$=''
240  IF op$ <> ''  THEN push op$         : op$=''
250  IF expr$(i)='+' THEN push(pop+pop)
260  IF expr$(i)='-' THEN push(-pop+pop)
270  IF expr$(i)='*' THEN push(pop*pop)
280  IF expr$(i)='/' THEN v=pop: push(pop/v)
290  IF expr$(i)='\' THEN push(1/pop)
300  IF expr$(i)='^' THEN v=pop: push(pop^v)
310  IF expr$(i)='#' THEN push(SQRT(pop))
320 END FOR i
330 PRINT pop
340 END DEFine calc
350 :
360 DEFine PROCedure push (v)
370  FOR j=9 TO 1 STEP -1: st(j+1)=st(j)
380  st(1)=v
390 END DEFine push
400 :
410 DEFine FuNction pop
420 LOCal v
430  v=st(1)
440  FOR k=1 TO 9: st(k)=st(k+1)
450 RETurn v
460 END DEFine pop

Calling `calc' procedure above:

Code: Select all

calc "8 3 4* 7++ 1 3/^"

gives 3

Tomas

[ql_freak]

Hi ql_freak,
As I have always wondered how expression evaluation works, `FORTRAN' probably first among languages getting that right and earning a huge fortune to IBM.

A good example can be found in Bjarne Stroustrups book "The C++ Programming Language". This expression parser calculator is the base of the expression parser in my "Coca" (albeit improved, supports "power of" and all C++ math functions with one parameter, AND all global variables removed). The parser in the current release of "Stroustrup" uses a "map" class (from C++ 11 standard library) for handling variables, older versions of "Stroustrup" handled the variables via a hash-table. The latter has the advantage, that it should easily be portable to C (the calculator doesn't use much C++ specialities, it's nearly pure C), which isn't possible with the current version.

BTW: FORTRAN (at least Fortran 77) does not have an expression parsing function (like val() from EJC). The Spectrum has such a function. I don't know, why it has been omitted in SuperBASIC. Principally it is supported, as you can enter an expression in interactive mode in channel #0, so there must be code in the ROM which parses such a string.

Here a small example for EJC which implements a simple calculator with an expression parser, using EJCs val() function. It's reentrant (I have had HOT_CHP()ed it without the 'I'-option for impure code and started it several times) and should be (as the manual states) also be ROMable (size of executable file is 21418 bytes):

Code: Select all

/* Simple QL/QDOS calculator with expression parser */

#include <stdio.h>
#include <math.h>
#include <val.h>

#define BUFSIZ 512
char buf[BUFSIZ]; /* input buffer */

int myerrno;

int main(argc,argv) int argc;char *argv[]; {
    char *in;
    double rslt;
    int rorre=0;

    printf("Simple QL calculator for evaluating expressions.\n");
    printf("Enter an expression like: 8+3*4+7^(1/3) - Fullstop to quit.\n");
    printf("The following preset variables may be used: x=PI and y=PI/2\n");
    printf("WARNING: Division by zero cannot be detected because of\n");
    printf("a bug in the math library(!).\n");

    /* An expression parser with the val() function of EJC: */
    for (;;) {
        printf(">");
        in=gets(buf);
        if (!strcmp(in,"."))
            break;
        printf("Result of %s=",in);
        /* Note: Following is WRONG! C is not C#, the printf() function is
                 NOT typesafe(!) in contrary to the C#-function
                 Console.WriteLine(string,string); */
        /* WRONG(!): printf(in,"=\n"); */

        myerrno=0; /* assume no error */
        /* A T T E N T I O N : */
        /* Following function val(...) is NOT Standard! It is a special
           function of EJC. I don't know any other C/C++ implementation
           which has (supports) this (or similar/kind of) function!) */
        rslt=val(in,&rorre,PI,PID2);

        if (rorre)
            printf("Error in expression\n");

        /* N O T E :   division by zero is _N_O_T_ detected! */
        /* This unfortunately cannot be corrected in EJC (and other
           compilers lack the val() function), as the standard
           error detection via matherr() (see below) does not
           work :-( */

        /* Math error detection (does not work on EJC): */
        else if (myerrno)
            printf("matherr() has detected an error (e.g. divide by zero)\n");

        else
            printf("%g\n",rslt);
    }
    /* Following is always required for "command line programs" on QDOS with
       Pointer Interface and the Lattice/EJC/PDQLC compiler, else you won't
       see the output, cause the PE will remove the window, as soon as the
       program ends. C68 handles this automatically: */

/* Not needed in this program, cause it is interactive:
#ifndef __C68__
    printf("ENTER to quit");
    getchar();
#endif
*/

}

/* Math error detection does not work (has a bug)! matherr() is never
called. Even if you write e. g. double d; d=3./0.; matherr() is not
called and d is set to 0. :-| This is also true for the inbuild
matherr function from the library. */
int matherr(x) struct exception *x; {
    if (x->type >= DOMAIN && x->type <= PLOSS)
        myerrno=x->type;
}

[tcat]

Hi Peter,

Your work is impressive, my routine is no match.

By referring to `FORTRAN', I meant that at compiler level it has the ability to translate maths formulas into executable code. But perhaps my memory fails me, last time used with `punch cards' and `punch tapes' at university many years ago.

Tomas

[pjw]

I am glad my post raised some interest at last. Very interesting story of yours with HP. I was challenged by ql_freak's below expression.

Code:
(8+3*4+7)^(1/3)

Postix equivalent

Code:
8 3 4* 7++ 1 3/^

Here is possibly buggy, but simplified postfix evaluator, but carries the idea

Very nice

QDOS/SMSQ has an in-built stack based calculator (see qa.op and qa.mop) which could be used in programs to implement some EVAL()-type functionality. If only math functions and variables are used it shouldnt be too hard. Converting infix to postfix, if required, is relatively trivial. But if one needed to use S*BASIC functions or other parts of the interpreter as well, that would be very hard to do within the scope of an EVAL function. However, there are other ways, depending on the degree of "programability" one was after. For example, one could use one instance of SBASIC to program another, communicating via pipes or shared memory. I suppose this could be made to work under QDOS too, if using Minerva.

[BSJR]

...Laurence Reeves, of Minerva fame, has written a very competent RPN calulator, ECalc, for the PC, but it isnt HP41-like, nor even programmable. Cant find it on the Web any more. Someone called Peter Lauridsen wrote a "Scientific Reverse Polish Notation Calculator" for the QL. I think its just called RPN_obj. It comes with source code. I dont know if its available for download anywhere, but I have a copy if anyone wants it to look at.

There is a RPN calculator by Ralf Biederman, an early PE tool and German Hilfe only, on the Miscellaneous page of Dilwyn's site. The Laurence Reeves package is also there.

Bob

[pjw]

Thanks, Bob