Announcement

Collapse
No announcement yet.

In writing a math expression parser

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • In writing a math expression parser

    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
    Last edited by Steven Pringels 3; 25 Apr 2008, 09:40 AM.
    So here we are, this is the end.
    But all that dies, is born again.
    - From The Ashes (In This Moment)

  • #2
    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
    Last edited by Eddy Van Esch; 25 Apr 2008, 10:32 AM.
    Eddy

    Comment


    • #3
      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

      Comment


      • #4
        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,

        Code:
        '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
        Last edited by Brad D Byrne; 25 Apr 2008, 12:07 PM. Reason: sp,

        Comment


        • #5
          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
          So here we are, this is the end.
          But all that dies, is born again.
          - From The Ashes (In This Moment)

          Comment


          • #6
            Originally posted by Steven Pringels 3 View Post
            ...... 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

            Comment


            • #7
              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.

              Comment


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

                Bye!
                -- The universe tends toward maximum irony. Don't push it.

                File Extension Seeker - Metasearch engine for file extensions / file types
                Online TrID file identifier | TrIDLib - Identify thousands of file formats

                Comment


                • #9
                  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
                  So here we are, this is the end.
                  But all that dies, is born again.
                  - From The Ashes (In This Moment)

                  Comment


                  • #10
                    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:
                    Code:
                    #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.
                    Daniel Corbier
                    uCalc Fast Math Parser
                    uCalc Language Builder
                    sigpic

                    Comment


                    • #11
                      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.

                      Comment


                      • #12
                        http://www.thinbasic.com/index.php?o...d=27&Itemid=66

                        See BINT32 (Basic Interpreter).
                        Free Power Basic sources included.
                        thinBasic programming language
                        Win10 64bit - 8GB Ram - i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

                        Comment

                        Working...
                        X