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 2020 - 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
----------------------------------------------------------------------