In writing a math expression parser

[Steven Pringels 3]

Hi,

I figured that writing a math expression parser isn't that easy but I started this pet-project anyway and came to the conclusion that it is better to convert the expression into a different format. Here is what came out (no code, but the idea).

It is already coded but can't post it because it's a part of a much bigger thing. Anyway, here is the idea.

We have the following expression

15 * (10 + (6 * 5) / 2)

which converts to

* 6 5 / 2 + 10 * 15

another example

10 + 1 * SQR(16)

would be

16 SQR * 1 + 10

This should evaluate much easier since there are no parenthesis anymore.

I guess this is what's called Polish Notation. Has anyone here done the same thing and used the same approach ?

Cheers

Steven

[Eddy Van Esch]

Hi Steven,

I haven't ever coded this, but somehow I have the impression that the Reverse Polish Notation seems easier to code (or maybe that's just because I am used to that from my old HP-41CV calculator).

Your line:
15 * (10 + (6 * 5) / 2)

Would convert to this:
6 {ENTER} 5 * 2 / 10 + 15 *

So the math operator always comes last. To me, this seems easier to 'drag' the previous result along.
You then would perform the math operation on Accumulator 1 and Accumulator 2.The result then goes into Accumulator 1, the new operand is stored in Accumulator 2, etc.

Another one:
(5 + 3) * (10 - 4)
becomes:
5 {ENTER} 3 + 10 {ENTER} 4 - *
The result of 5+3 is stored on 'the stack' because after '10', {ENTER} was 'pressed'.
You would have to use a stack to store intermediary results.

Kind regards

[Pierre Bellisle]

Hi Steven,

About math expression parser,
in the event that you are not aware of it,
Erik Christensen did something great a while ago...

Math expression evaluator for PB Windows

[Brad D Byrne]

here's a bit different approach that should lead to the fastest Expression Evaluator ever if anyone interested,

it's just a start, I believe it's my most recent version, I wrote it years ago, it reads the expression as written and computes as soon as possible, and set up in way that it can easily convert to asm, it's just a start the other math operands need to be added,

'Reversely Expression Evaluator - Brad Byrne
'PBWin 7.02
'this is a beginning for an interpreter level math expression evaluator, after searching for
'examples, all I found first parsed out the operands and stored the to be evaluated values,
'personally I thought that was ineffiecient when if we do it right, we should be able to
'compute the values as we go, keeping the location of them close by,
'
'this code is just a start, it only walks up and down the parenthesis tree, but the same
'technique can be applied to the remaining hierarchy of math functions.
'
'Anyone want to help finish this? it could be fun!
'and Honest Critique welcomed!
'
'I left this table here for referance


'ASCII TABLE
'    0   nul      16 _ dle ^P   32     48 0   64 @   80 P   96 `  112 p
'    1 _ soh ^A   17 _ dc1 ^Q   33 !   49 1   65 A   81 Q   97 a  113 q
'    2 _ stx ^B   18 _ dc2 ^R   34 "   50 2   66 B   82 R   98 b  114 r
'    3 _ etx ^C   19 _ dc3 ^S   35 #   51 3   67 C   83 S   99 c  115 s
'    4 _ eot ^D   20 ¶ dc4 ^T   36 $   52 4   68 D   84 T  100 d  116 t
'    5 _ enq ^E   21 § nak ^U   37 %   53 5   69 E   85 U  101 e  117 u
'    6 _ ack ^F   22 _ syn ^V   38 &   54 6   70 F   86 V  102 f  118 v
'    7 _ bel ^G   23 _ etb ^W   39 '   55 7   71 G   87 W  103 g  119 w
'    8 _ bs  ^H   24 _ can ^X   40 (   56 8   72 H   88 X  104 h  120 x
'    9   tab ^I   25 _ em  ^Y   41 )   57 9   73 I   89 Y  105 i  121 y
'   10   lf  ^J   26 _ eof ^Z   42 *   58 :   74 J   90 Z  106 j  122 z
'   11   vt  ^K   27 _ esc ^[   43 +   59 ;   75 K   91 [  107 k  123 {
'   12   np  ^L   28 _ fs  ^\   44 ,   60 <   76 L   92 \  108 l  124 |
'   13   cr  ^M   29 _ gs  ^]   45 -   61 =   77 M   93 ]  109 m  125 }
'   14   so  ^N   30 - rs  ^^   46 .   62 >   78 N   94 ^  110 n  126 ~
'   15 ¤ si  ^O   31  us   ^_   47 /   63 ?   79 O   95 _  111 o  127

'reversely expression evaluator test code - Brad Byrne
#COMPILE EXE
#INCLUDE "WIN32API.INC"

DECLARE CALLBACK FUNCTION CallBackFunc()
GLOBAL PrgrmCode AS STRING, fState AS STRING

FUNCTION Interpret() AS LONG
DIM v AS BYTE PTR
DIM NestPtr AS LONG, i AS LONG
DIM TempValStr AS STRING, syntaxErrStr AS STRING, NestStr(100) AS STRING
v = STRPTR(PrgrmCode)

FOR i = 0 TO LEN(PrgrmCode)-1
ON @v[i]-39 GOTO openNest, closeNest, MultiplyIt, AddIt, SkipIt, SubtractIt, ParseNumeric, DivideIt, _
ParseNumeric,ParseNumeric,ParseNumeric,ParseNumeric,ParseNumeric,ParseNumeric,ParseNumeric,ParseNumeric, _
ParseNumeric,ParseNumeric
ON @v[i]-93 GOTO RaiseToPower
GOTO DoneIt
SkipIt:
NEXT
DoneIt:
IF i>= LEN(PrgrmCode)-2 THEN syntaxErrStr = "got to end" ELSE syntaxErrStr = _
"syntax err: invalid Char, supports (0-9.-+/*^) only "
GOTO iExit
'----------------------------------------------------------
ParseNumeric: 'Numeric 0-9. loop resolve TempValStr
TempValStr = TempValStr + CHR$(@v[i])
GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
RaiseToPower:
TempValStr = TempValStr + CHR$(@v[i])
'GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
DivideIt:
TempValStr = TempValStr + CHR$(@v[i])
'GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
MultiplyIt:
TempValStr = TempValStr + CHR$(@v[i])
'GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
SubtractIt:
TempValStr = TempValStr + CHR$(@v[i])
'GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
AddIt:
TempValStr = TempValStr + CHR$(@v[i])
'GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
OpenNest:
NestStr(NestPtr)= NestStr(NestPtr) + TempValStr
INCR NestPtr
TempValStr =""
fState = "OpenNest"
GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------
CloseNest:
NestStr(NestPtr)= NestStr(NestPtr) + TempValStr
fState = "CloseNest"
GOSUB ShowMsg
TempValStr =""
NestStr(NestPtr)=""
DECR NestPtr
NestStr(NestPtr) = NestStr(NestPtr) + "z"
fState = "returnNest"
GOSUB ShowMsg
GOTO SkipIt
'----------------------------------------------------------


ShowMsg:
MSGBOX "i " + STR$(i)+ $CRLF + _
"@v " + STR$(@v[i])+ $CRLF + _
"NestStr(0) " + NestStr(0)+ $CRLF + _
"NestStr(1) " + NestStr(1)+ $CRLF + _
"NestStr(2) " + NestStr(2)+ $CRLF + _
"NestStr(3) " + NestStr(3)+ $CRLF + _
"NestStr(4) " + NestStr(4)+ $CRLF + _
"NestPtr " + FORMAT$(NestPtr) + $CRLF + $CRLF + _
"State " + fState + $CRLF + _
"TempValStr " + TempValStr
RETURN

iExit:

SyntaxErr:
MSGBOX syntaxErrStr
END FUNCTION


FUNCTION PBMAIN
LOCAL Count&, hDlg1&
PrgrmCode = "(3+5-(3/(2.5+8*(3*3^2)-2)+7)/2)" + $CRLF

DIALOG NEW 0, "Reversely Expression Evaluator - Brad Byrne",150,50, 350, 150, %ws_sysmenu , TO hDlg1&
CONTROL ADD TEXTBOX ,hDlg1&,1000,PrgrmCode,10,10,300,80,%ES_multiline OR %WS_VSCROLL _
OR %WS_HSCROLL OR %ES_AUTOVSCROLL OR %ES_WANTRETURN ,%WS_EX_CLIENTEDGE
CONTROL ADD BUTTON, hDlg1, 100, "&Run", 280, 100, 50, 14
DIALOG SHOW MODELESS hDlg1&, CALL CallBackFunc()

DO
DIALOG DOEVENTS TO Count&
LOOP WHILE Count&
END FUNCTION

CALLBACK FUNCTION CallBackFunc()
LOCAL hDC&, ps AS paintstruct

SELECT CASE CBMSG
CASE %WM_COMMAND
SELECT CASE CBCTL
CASE 100
IF CBCTLMSG = %BN_CLICKED THEN

CALL Interpret()
END IF
END SELECT

CASE %WM_DESTROY
PostQuitMessage 0
FUNCTION = %TRUE

END SELECT
END FUNCTION

[Steven Pringels 3]

Oops

Ok, I noticed after thinking about this - while driving home you often put things in a different perspective - that his is not Polish Notation. My attempt here is to evaluate the precedence of operators first and by doing this evaluate the
most inner expression between parenthesis.

I noticed a bug which I found while taking the example on wikipedia for Polish Notation.

Polish Notation uses a stack principal which requires multiple passed to go through a math expression. I would like to evaluate the math from left to right with one single pass.

Back to the drawing board.

Thanks for the code Brad.

Steven

[Brad D Byrne]

...... I would like to evaluate the math from left to right with one single pass.

Steven

Steven, the code I showed you does just that, it reads the expression and evaluates the parts as doable, only pushing the undoable parts onto a stack(so to speak) until they are doable, then it reverses direction and resolves the rest reading back down,

if you look at it, it will be easy to add the other functions and order of presidence in similar manner

[Donald Darden]

Having written my own version, I can tell you that what helps is to scan the string backwards for an included "(" symbol, then from there, scan forward to the first ")". This will be the intermost paren pair that needs to be resolved first. You can use INSTR() to perform this search.

The problem becomes more difficult if you decide to include functions, such as SQR(), ABS(), SGN(), INT(), SIN(), RND(), and so on, or if you want to use variable names, such as A, B, TAX, TOTAL, or PI in your expressions. An interesting byproduct of having programmed the old Commodore C64 PC was that an interpreter will allow you to write an expression to the screen, then execute it as though a part of your program, then resume operating with the result passed to a variable, so you could use the interpreter to do the parsing for you, and the inclusion of variables and defined functions were dealt with automatically.

[Marco Pontello]

Another option, using Lua and a minimal PB interface:
PowerBLua: runtime expression parsing made simple

Bye!

[Steven Pringels 3]

Thanks for all the replies.

I will attempt a different approach and *try* to implement the Polish Notation
or Reverse Polish Notation as-is. See what it brings.

Cheers

Steven

[Daniel Corbier]

uCalc Fast Math Parser

If you want a ready-made math parser that is free, and easy to implement in PowerBASIC, then try uCalc Fast Math Parser. The web site promotes the commercial license, which may be priced out of reach for some, but if you download it and look at the help file, you will find that there is also a Free License, for those who just want the basics and don't want to pay for it. When I say basics, you still have the full set of functions and operators, and you can define your own variables and functions. It uses the same fast parsing engine that powers the commercial license.

Here's a simple example in PB:

#Include "uCalcPB.bas"

Function PBMain()
   Print ucEval("5+sin(2)^8")
End Function

Speaking of Reverse Polish notation, check out uCalc Language Builder, which is closely related to uCalc FMP. Download it and check out RPN.uc, which changes the input syntax to Reverse Polish Notation.

[Donald Darden]

In the old days, people would have urged you on, because writing code was so new that we could not find decent alternatives. Now, people redirect you to use that has been developed by others, which is a way of telling you not to waste your time.

But learning how to do something is a necessary step up, like building a bird house or dog house before trying to design and build a people house.

[Eros Olmi]

http://www.thinbasic.com/index.php?option=com_docman&task=cat_view&gid=27&Itemid=66

See BINT32 (Basic Interpreter).
Free Power Basic sources included.