'===========================================================================
' Subject: CONVERT INFIX TO POSTFIX (RPN)    Date: 02-15-97 (10:00)       
' Author:  The ABC Programmer                Code: QB, QBasic, PDS        
' Origin:  voxel@freenet.edmonton.ab.ca    Packet: ALGOR.ABC
'===========================================================================
'***************************************************************************
' INFIX TO POSTFIX EXPRESSION CONVERTER programmed by William Yu (02/97)
'
'       Converts Infix:  ((A + 5) / B - 2) * C
'     To Postfix (RPN):  A 5 + B / 2 - C *
'
' Also available in ALGOR.ABC is the RPN (Postfix) evaluator.
' For the stack in this case, only the operators "()+-*/^" are stored
' instead of the operands for the RPN Evaluator.
'
' This program was converted to BASIC by William Yu using a Pascal template
' Referenced from:
'            Larry Nyhoff & Sanford Leestma
'            Data Structures and Program Design in Pascal (2nd Edition)
'            Pages 204-209.
'
' With some ingenuity, you could simply make this to an Infix evaluator.
'***************************************************************************
DEFINT A-Z
DECLARE SUB ProcessOperator (Operator AS STRING, Stack%)
DECLARE FUNCTION Priority% (Operator AS STRING)
DECLARE SUB Pop (Stack AS INTEGER, Element AS STRING)
DECLARE SUB ProcessRightParen (Stack%, ErrorCode%)
DECLARE SUB ConvertToRPN (Expression AS STRING)
DECLARE SUB Push (Stack AS INTEGER, Element AS STRING)

CONST FALSE = 0
CONST TRUE = NOT FALSE
CONST Max = 25            ' Maximum number of operators to be stored
                          ' in the stack at one time.  eg. if you have
                          ' a lot of ((((((((( brackets in your expression
                          ' the stack size should be adjusted.

DIM SHARED Element(1 TO Max) AS STRING * 1
DIM Expression AS STRING

CLS

' NOTE:  2(4 + 5) will not parse properly (include the '*' sign)
'  USE:  2*(4 + 5) instead.

Expression = "(A-B)*(C-(D+E)^F)"    ' Start with the Infix notation

'Expression = "((A+B)"              '<- Here's an error in expression
'Expression = "WowWee*(How+Does^Programming)-This*Work"
'Expression = "((123 + 39^3 * (43 - 89) / 10 - ((90 - 34) * 3)))"

PRINT "  The infix: "; Expression
PRINT "Now Postfix: ";
ConvertToRPN Expression              ' Then get the Postfix (RPN) expression

END

SUB ConvertToRPN (Expression AS STRING)
'********************************************************
'   Input:  Infix expression
' Purpose:  Convert Expression to RPN
'  Output:  To screen, the Postfix (RPN) Expression
'    Note:  Uses procedures Priority, ProcessRightParen
'           ProcessOperator, and stack-processing
'********************************************************

DIM Token AS STRING * 1

  Stack = 0               ' Initialize an empty stack
  ErrorCode = FALSE
  Signs$ = " ()+-*/^"

  I = 1
  Token = LEFT$(Expression, 1)

  WHILE (NOT ErrorCode) AND (I <= LEN(Expression))
    Valid = FALSE
    FOR X = 1 TO LEN(Signs$)
      IF Token = MID$(Signs$, X, 1) THEN Valid = TRUE: EXIT FOR
    NEXT X
    IF Valid THEN
      PRINT " ";
      SELECT CASE Token
        CASE " "                       '{* Skip Blanks and do nothing *}
        CASE "("                       '{* Left parenthesis           *}
          Push Stack, Token
          LOCATE , POS(CSRLIN) - 1     '{* Just to make it look nice  *}
        CASE ")"                       '{* Right parenthesis          *}
          ProcessRightParen Stack, ErrorCode
        CASE "+", "-", "*", "/", "^"   '{* Arithmetic operator        *}
          ProcessOperator Token, Stack
      END SELECT
    ELSE                               '{* Operand *}
      PRINT Token;
    END IF
    I = I + 1                          '{* Get next token and process it *}
    Token = MID$(Expression, I, 1)
  WEND

  '{* Pop and display operators on the stack *}
  WHILE Stack <> 0 AND NOT ErrorCode
    Pop Stack, Token
    IF Token <> "(" THEN
      PRINT Token;
    ELSE
      ErrorCode = TRUE
    END IF
  WEND

  IF ErrorCode THEN
    PRINT "<<< Error in infix expression >>>"
  END IF

END SUB

SUB Pop (Stack AS INTEGER, Element AS STRING)
'----------------------------------------------
'  Return the top element on the stack.
'----------------------------------------------

IF Stack = 0 THEN
  PRINT " *** Attempt to pop from an empty stack ***"
ELSE
  Element = Element(Stack)
  Stack = Stack - 1
END IF

END SUB  '{* Pop *}

FUNCTION Priority% (Operator AS STRING)
'**********************************************************
'   Input:  The Character Operator
' Purpose:  Find the priority of Operator, and arithmetic
'           operator of (.
'  Output:  Returns priority (0 - 2) of Operator.
'**********************************************************
 
  SELECT CASE Operator
    CASE "("            ' Not so great
      Priority = 0
    CASE "+", "-"
      Priority = 1
    CASE "*", "/"
      Priority = 2
    CASE "^"            ' Greatest priority (Exponential)
      Priority = 3
  END SELECT

END FUNCTION

SUB ProcessOperator (Operator AS STRING, Stack)
'*********************************************************************
'   Input:  A Character denoting an arithmetic Operator, and a
'           stack of operators.
' Purpose:  Process an arithmetic operator.  Operators are popped
'           from the stack until the stack becomes empty or an
'           operator appears on the top of the stack whose priority
'           is less than or equal to that of the Operator.  Operator
'           is then pushed onto the stack.
'  Output:  Modified stack position.
'*********************************************************************

DIM TopOperator AS STRING * 1

  DonePopping = FALSE

  DO
    IF Stack = 0 THEN
      DonePopping = TRUE
    ELSE
      Pop Stack, TopOperator
      IF Priority(Operator) <= Priority(TopOperator) THEN
        PRINT TopOperator;
      ELSE
        Push Stack, TopOperator
        DonePopping = TRUE
      END IF
    END IF
  LOOP UNTIL DonePopping
  Push Stack, Operator

END SUB

SUB ProcessRightParen (Stack, ErrorCode)
'******************************************************************
'   Input:  The stack position
' Purpose:  Pop and display operators from Stack until a left
'           parenthesis is on top of the stack; it too is popped,
'           but not displayed.
'  Output:  Modified stack position, and ErrorCode, which is true
'           if the stack becomes empty with no left parenthesis
'           being found.
'******************************************************************

DIM TopToken AS STRING * 1

  DO
     IF Stack = 0 THEN
       ErrorCode = TRUE
     ELSE
       Pop Stack, TopToken
       IF TopToken <> "(" THEN PRINT TopToken;
     END IF
  LOOP UNTIL TopToken = "(" OR ErrorCode

END SUB

SUB Push (Stack AS INTEGER, Element AS STRING)
'----------------------------------------------
'  Fill stack with Element
'----------------------------------------------

Stack = Stack + 1
IF Stack > Max THEN
  PRINT " *** Attempt to push on a full stack ***"
ELSE
  Element(Stack) = Element
END IF

END SUB '{* Push *}