' Parsing/RPN calculator algorithm
DECLARE SUB MakeEmpty (S AS ANY)
DECLARE SUB Push (X AS SINGLE, S AS ANY)
DECLARE SUB PrintStack (S AS ANY)
DECLARE SUB EvalRPN (Expr$)
DECLARE FUNCTION Empty% (S AS ANY)
DECLARE FUNCTION Pop! (S AS ANY)

CONST MAXINDEX = 63

TYPE TNumStack
  TopIndex AS INTEGER
  Elems(MAXINDEX) AS SINGLE
END TYPE

EvalRPN ("3 4 2 * 1 5 - 2 3 ^ ^ / +")
END

FUNCTION Empty% (S AS TNumStack)
  Empty% = S.TopIndex > MAXINDEX
END FUNCTION

SUB EvalRPN (Expr$)
  DIM S AS TNumStack
  MakeEmpty S
  PRINT "Input", "Operation", "Stack after"
  ' SP% - start position of token
  ' DP% - position of delimiter
  DP% = 0
  DO
    SP% = DP% + 1
    DP% = INSTR(DP% + 1, Expr$, " ")
    IF DP% <> 0 THEN
      TE% = DP% - 1
      Token$ = MID$(Expr$, SP%, DP% - SP%)
    ELSE
      Token$ = MID$(Expr$, SP%, LEN(Expr$) - SP% + 1)
    END IF
    PRINT Token$,
    IF Token$ = "*" THEN
      PRINT "Operate",
      Second = Pop(S): First = Pop(S)
      Push First * Second, S
    ELSEIF Token$ = "/" THEN
      PRINT "Operate",
      Second = Pop(S): First = Pop(S)
      Push First / Second, S
    ELSEIF Token$ = "-" THEN
      PRINT "Operate",
      Second = Pop(S): First = Pop(S)
      Push First - Second, S
    ELSEIF Token$ = "+" THEN
      PRINT "Operate",
      Second = Pop(S): First = Pop(S)
      Push First + Second, S
    ELSEIF Token$ = "^" THEN
      PRINT "Operate",
      Second = Pop(S): First = Pop(S)
      Push First ^ Second, S
    ELSE
      PRINT "Push",
      Push VAL(Token$), S
    END IF
    PrintStack S
  LOOP UNTIL DP% = 0
  PRINT "Final answer: "; Pop(S)
  IF NOT Empty(S) THEN
    PRINT "Error, too many operands: ";
    PrintStack S
    STOP
  END IF
END SUB

SUB MakeEmpty (S AS TNumStack)
  S.TopIndex = MAXINDEX + 1
END SUB

FUNCTION Pop (S AS TNumStack)
  IF Empty%(S) THEN
    PRINT "The stack is empty."
    STOP
  ELSE
    Pop = S.Elems(S.TopIndex)
    S.TopIndex = S.TopIndex + 1
  END IF
END FUNCTION

SUB PrintStack (S AS TNumStack)
  FOR Ptr% = S.TopIndex% TO MAXINDEX
    PRINT USING "######.###"; S.Elems(Ptr%);
  NEXT Ptr%
  PRINT
END SUB

SUB Push (X AS SINGLE, S AS TNumStack)
  IF S.TopIndex = 0 THEN
    PRINT "The stack is full."
    STOP
  ELSE
    S.TopIndex = S.TopIndex - 1
    S.Elems(S.TopIndex) = X
  END IF
END SUB