Entry

BBCBASIC: Data structure: Simple: Suffix: How do you evaluate an RPN expression? [postfix]

Jan 5th, 2007 08:22
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 21 November 2006 - 08:04 pm -------------------

BBCBASIC: Data structure: Simple: Suffix: How do you evaluate an RPN 
expression?  [postfix]

For simplicity, in this simple version the restrictions are

 1. -only single digits assumed, so intermediate results should be
     smaller or equal to 9 all the time during the calculation.

 2. -only binary operators (so taking all the time 2 values off the top
     of the stack)

 3. Please take spaces away.

     so "2*2+5" is OK, 

     but "2 * 2  + 5" is not

 4. all lines in the program are single lines, so all on one line

===

Steps: Overview:

 1. -Create a new BBCBASIC application

 2. -Fill in the following code

--- cut here: begin --------------------------------------------------

 infix$ = "2*2+5"

 suffix$ = "22*5+"

 PRINT; "infix = "; infix$

 PRINT; "suffix = "; suffix$

 PRINT; "value = "; FNStringConvertSuffixEvaluateS( suffix$ )

 PRINT

 infix$ =  "1*2+1-3+1+4*2"

 suffix$ = "12*1+3-1+42*+"

 PRINT; "infix = "; infix$

 PRINT; "suffix = "; suffix$

 PRINT; "value = "; FNStringConvertSuffixEvaluateS( suffix$ )

 PRINT


 END

 :

 :

 :

 DEF FNStringConvertSuffixEvaluateS( expression$ )

 LOCAL characterExpression$

 LOCAL expressionI

 LOCAL operand$

 LOCAL operand1D

 LOCAL operand2D

 LOCAL operandAll$

 LOCAL operandStack$

 LOCAL operator$

 LOCAL operatorAll$

 LOCAL posOperandI

 LOCAL posOperatorI

 LOCAL valueD

 REM initialize the evariables you will use

 characterExpression$ = ""

 expressionI = 1 - 1

 operand$ = ""

 operand1D = 0

 operand2D = 0

 operandAll$ = "0123456789"

 operandStack$ = ""

 operator$ = ""

 operatorAll$ = "-+*/^"

 posOperandI = 0

 posOperatorI = 0

 valueD = 0

 :

 REM while your given suffix string is not empty
 WHILE ( expressionI < LEN( expression$ )  )

   REM goto next character
   expressionI = expressionI + 1

   REM get the current front character of that suffix string
   characterExpression$ = MID$( expression$, expressionI, 1 )

   REM check if you find an operator you defined (e.g. '*', '+', ...)
   posOperatorI = INSTR( operatorAll$, characterExpression$ )

   REM check if you find an operand you defined (e.g. digit 0, 1, ...)
   posOperandI = INSTR( operandAll$, characterExpression$ )

   REM if you did not find any of your defined operators or operands
   REM then error
   IF ( posOperatorI = 0 ) AND ( posOperandI = 0 ) THEN PRINT; 
characterExpression$; " undefined character: "; 
characterExpression$; ": Please build your expressions currently 
from "; operatorAll$; operandAll$ : STOP : = -1E32

   REM if your current character is an operand
   IF ( posOperandI <> 0 ) THEN

     operand$ = characterExpression$

     REM show current operand
     PRINT; "operand = "; operand$

     REM put your character in front (=top here) of the stack$
     operandStack$ = operand$ + operandStack$

   ELSE

     REM assume binary operator,
     REM so get value of 2 operands on top stack
     operand2D = VAL ( MID$( operandStack$, 1, 1 ) )

     operand1D = VAL ( MID$( operandStack$, 2, 1 ) )

     operator$ = characterExpression$

     REM show current operator
     PRINT; "operator = "; operator$

     REM show current left operand
     PRINT "operand1D = "; operand1D

     REM show current right operand
     PRINT "operand2D = "; operand2D

     REM remove first 2 characters from (=top here) operand stack,
     REM as they are handled now
     operandStack$ = MID$( operandStack$, 3, LEN( operandStack$ ) - 2 )

     REM depending on which operator you found, do something
     CASE operator$ OF

       WHEN "-"

         valueD = operand1D - operand2D

       WHEN "+"

         valueD = operand1D + operand2D

       WHEN "*"

         valueD = operand1D * operand2D

       WHEN "^"

         valueD = operand1D ^ operand2D

     ENDCASE

     PRINT; "valueD is now = "; valueD

     REM put the current calculated value back
     REM in front (=top here) of stack
     operandStack$ = STR$( valueD ) + operandStack$

   ENDIF

   REM show the current operand stack
   PRINT; "operandStack$ = "; operandStack$

   REM REPEAT UNTIL GET

 ENDWHILE

 = valueD

 :

--- cut here: end ----------------------------------------------------

 3. -Run this code

     That should show:

      infix$ = "2*2+5"

      suffix$ = "22*5+"

      value = 9

     and the other example

     infix$ =  "1*2+1-3+1+4*2"

     suffix$ = "12*1+3-1+42*+"

     value = 9

===

Internet: see also:

---

Algorithm: Expression: Infix: Convert: Postfix: Overview: How convert 
infix to postfix expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26071/fid/585

----------------------------------------------------------------------