I'm currently working on the shunting yard algorithm in BASIC and it looks like a very simple algorithm. It feels a lot more complex in BASIC because of the stack juggling that I'm doing. I decided that it would be much easier if I wrote an abstraction for stacks so that I could focus on just the code. This was similar to my hashmap implementation as I was adding a data structure ontop of BASIC multivalue data.
Note: Now that I've written it, I can say that this made it much easier.
The first thing is to define the contract that I wanted:
EQU STACK.SIZE TO 11
DIM STACK(STACK.SIZE)
*
MAT STACK = ''
*
FOR I = 1 TO 10
CALL STACK.PUSH(MAT STACK,STACK.SIZE,I)
NEXT I
*
FOR I = 1 TO 15
CALL STACK.POP(MAT STACK,STACK.SIZE,VALUE)
PRINT VALUE
NEXT I
*
END
*
I use the first attribute of the array to hold that stack counter. This means that the capacity of the stack is always the 1 less than the size you define. This also has the effect that the caller program is always aware of what the stack counter is at.
The stack counter will be the current position that will be popped.
PRINT STACK(STACK(1))
This will therefore be the way to do a peek.
Here is the STACK.PUSH:
DIM STACK(SIZE)
*
STACK.CTR = STACK(1)
*
IF STACK.CTR = '' THEN
STACK(1) = 1
STACK.CTR = 1
END
*
IF NOT(NUM(STACK.CTR)) THEN
PRINT 'Invalid stack counter in (1).'
STOP
END
*
IF STACK.CTR >= SIZE THEN
PRINT 'Stack exceeded, maximum capacity is: ' : SIZE - 1
STOP
END
*
STACK.CTR = STACK.CTR + 1
*
STACK(STACK.CTR) = VALUE
STACK(1) = STACK.CTR
*
RETURN
Luckily implementing a stack is very easy.
Now for the STACK.POP:
DIM STACK(SIZE)
*
VALUE = ''
*
STACK.CTR = STACK(1)
*
IF STACK.CTR = '' THEN
PRINT 'Nothing to pop.'
STOP
END
*
IF NOT(NUM(STACK.CTR)) THEN
PRINT 'Invalid stack counter in (1).'
STOP
END
*
IF STACK.CTR <= 1 THEN
PRINT 'Nothing to pop.'
STOP
END
*
VALUE = STACK(STACK.CTR)
*
STACK(1) = STACK.CTR - 1
*
RETURN
This assumes that calling function is checking before doing a POP. The program will hard stop if there is nothing to pop.