6. Parentheses, scientific notation and unary minus

The following important mathematical issues are parentheses and the unary minus. Parentheses are easy to implement because of the evaluator structure we are using. The function Eval will need to do the following. First it has to search only for operators outside parentheses and evaluate the expression parts if found. If not, the Eval function must check whether the expression is enclosed by parentheses, remove them and evaluate the expression.

Parentheses
To check only for operators outside parameters, we will create a modified version of the function InstrREV, called InstrP. This function counts the number of parentheses open and close that it encounters while searching for an operator. If there are more parentheses open than close, we are inside parentheses. If there are just as much parentheses open as close, we are outside parentheses. And if there are less parentheses open than close, there is a syntax error in the expression.

Function instrP
SUB instrP(source:STRING, search:STRING, start:INT), INT
    'this sub searches for the LAST string search in the string
    'source, reverse of the function instr(). The sub returns 0 if
    'the search could not be found. Also this function neglects
    'content between parenthesis () in source
    INT n, bopen, bclose
    STRING sign

    n=start
    IF n>LEN(source) THEN n=LEN(source)-LEN(search)+1
    bopen=0     :'number of parenthesis open (
    bclose=0    :'number of parenthesis close )
    DO
        sign = MID$(source, n, LEN(search))
        'if search is found and outside parentheses then return n
        IF (sign=search) AND (bopen=bclose) THEN RETURN n
        IF LEFT$(sign,1)="(" THEN bopen++
        IF LEFT$(sign,1)=")" THEN bclose++
        n--
    UNTIL (n <= 0)
    
    'if the string search is not found, then return 0
    RETURN 0
ENDSUB


If there are no operators outside parentheses in the expression but there are parentheses at start and end of the expression, then we have to remove these and evaluate the remaining expression.

IF LEFT$(expr,1)="(" AND RIGHT$(expr,1)=")"
    'remove parentheses at start and end of the expression,
    'for example "(2+3)" -> "2+3"
    expr = MID$(expr,2,LEN(expr)-2)
    RETURN Eval(expr)
ENDIF


Scientific notation
When values are becoming larger and larger, it is handy to use the scientific notation. For example "200000000" can be written as "2E8", what means 2 times ten to the power 8. With the scientific notation, we encounter the unary plus and minus, like in "1.22E-4" and "3.0E+4". In the next code example we will add the scientific notation "E".

Unary minus
The unary minus is a special case of the minus. A unary minus is no operator but just the sign of a negative value. For example in the expression "2 * -4.5" the minus belongs to the value "-4.5", and is no operator. Our current evaluator will evaluate this expression as "(2 * ) - (4.5)" what will give a wrong answer.

Therefore, if we we find an operator "+" or "-", we have to check whether this is indeed an operator, or an unary plus or minus. In the last case it must be neglected. We will create a function called isOperator() that will check if a found "+" or "-" is an operator or and unary plus or minus.

Function isOperator
SUB isOperator(expr:STRING, op:CHAR, n:INT), INT
    'This sub checks of the operator at postion n in expr is a
    'legal operator. For example the "+" in "2.3E+3" is no operator,
    'and the "-" in "3 * -2.5" is no operator but a unary minus
    STRING sign
    
    IF op="+"
        IF UCASE$(MID$(expr,n-1,1))="E"
            IF n>2
                IF INSTR("1234567890.", MID$(expr,n-2,1))>0
                    'for example "2.52E+4"
                    RETURN FALSE
                ENDIF
            ENDIF
        ENDIF
        RETURN TRUE
    ENDIF
    
    IF op="-"
        IF n=1
            'this is an unary minus, at the first position of the expr
            'for example "-3.4 / 6"
            RETURN FALSE
        ELSE
            'check for an unary minus (for example 2*-3  or  2.5E-6)
            'check the characters before the minus
            sign = LEFT$(expr,n-1)
            sign = RIGHT$(RTRIM$(sign),1)
            IF INSTR("+-/*^", sign)>0
                'For example "3.5 * -2"
                RETURN FALSE
            ENDIF
            IF UCASE$(MID$(expr,n-1,1))="E" AND n>2
                IF INSTR("1234567890.", MID$(expr,n-2,1))>0
                    'for example "2.3E-4"
                    RETURN FALSE
                ENDIF
            ENDIF
        ENDIF
        RETURN TRUE
    ENDIF
    
    'no problems found, the operator is indeed an operator.
    RETURN TRUE
ENDSUB


Because there is now an option that a found operator not really is an operator, we also need an extra loop. If an operator is found that is no operator, we have to check again if there is another one. The loop looks like:

FOR n=1 TO 6
    operator = MID$("-+/*^E", n, 1)
    
    'search for this operator in expr
    pos = InstrP(UCASE$(expr), operator, 255)
    WHILE pos>0
        IF isOperator(expr, operator, pos)=TRUE
        
            '... evaluate it and return
            
        ENDIF
        
        'if this operator is not evaluated, search for another one
        IF pos>0 THEN pos=instrP(UCASE$(expr), operator, pos-1)
    WEND
NEXT n

Example 3
The complete source code for the third example is now as follows. This evaluator supports the operators + - * / ^ E and parentheses ( ).

Example 3
/*
Recursive expression parser, Example 3.
Written with IBasic Professional
By Jos de Jong, may 2006

Supports expressions with operators + - * / ^ E and parentheses ( )
*/
AUTODEFINE "Off"
SETPRECISION 5
DEF inputexpr:STRING

OPENCONSOLE

'print some examples of expressions with their answers
PRINT "Expression Calculator"
PRINT ""
PRINT "You can use + - * / ^ E and parentheses ( )"
PRINT "Enter an expression and press Enter to calculate it."
PRINT "Enter an empty expression to quit"
PRINT ""
PRINT "Examples:"
PRINT "2 + 3 * -4 = ", Eval("2 + 3 * -4")
PRINT "2 + 3 / 4 - 5= ", Eval("2 + 3 / 4 - 5")
PRINT "2.5 ^ 3.25 - 5E2 / 100 = ", Eval("2.5 ^ 3.25 - 5E2 / 100 ")
PRINT "(1.5+2.5) * (3+4) = ", Eval("(1.5+2.5) * (3+4)")
PRINT ""
DO
    'ask the user to enter an expression. After this the expression
    'will be evaluated and the answer will be printed
    INPUT ">>", inputexpr
    IF RTRIM$(inputexpr)<>""
        PRINT "    Ans = ", Eval(inputexpr)
        PRINT ""
    ENDIF
UNTIL RTRIM$(inputexpr)=""

'end the program
CLOSECONSOLE
END

'_____________________________________________________________________
SUB Eval(Expression:STRING), DOUBLE
    DEF pos, n:INT
    DEF expr:STRING
    DEF part1, part2:STRING
    DEF operator:STRING
    
    'remove spaces at start and end of the expression
    expr = LTRIM$(RTRIM$(Expression))
    
    FOR n=1 TO 6
        'choose an operator
        '(for each loop choose the following of the five operators)
        operator = MID$("-+/*^E", n, 1)
        
        'search for the last occurance of this operator outside
        'parentheses
        pos = InstrP(UCASE$(expr), operator, 255)
        WHILE pos>0
            'Check if the found operator realy is an operator
            '(and not a unary plus or minus)
            IF isOperator(expr, operator, pos)=TRUE
                'there is an operator found at position pos. Split up
                'the expression in two parts and calculate the result
                'of that two parts. Then calculate the result for the
                'complete expression.
                part1 = LEFT$(expr, pos-1)
                part2 = RIGHT$(expr, LEN(expr)-pos)
                
                'now execute the calculation between left and right
                'part, and return the answer
                SELECT operator
                    CASE "-"
                        RETURN Eval(part1) - Eval(part2)
                    CASE "+"
                        RETURN Eval(part1) + Eval(part2)
                    CASE "/"
                        RETURN Eval(part1) / Eval(part2)
                    CASE "*"
                        RETURN Eval(part1) * Eval(part2)
                    CASE "^"
                        RETURN Eval(part1) ^ Eval(part2)
                    CASE "E"
                        RETURN Eval(part1) * 10 ^ Eval(part2)
                ENDSELECT
            ENDIF
            
            'the found operator was no operator,
            'search if there is another operator before this one
            IF pos>0 THEN pos=instrP(UCASE$(expr), operator, pos-1)
        WEND
    NEXT n
    
    'check if the expression starts and ends with parentheses
    IF LEFT$(expr,1)="(" AND RIGHT$(expr,1)=")"
        'remove parentheses at start and end of the expression,
        'for example "(2+3)" -> "2+3"
        expr = MID$(expr,2,LEN(expr)-2)
        RETURN Eval(expr)
    ENDIF
    
    'there are no more operators left in the expression, and the
    'expression is not solved yet so the expression must be a value
    'return the value
    RETURN VAL(expr)
ENDSUB

'_____________________________________________________________________
SUB instrP(source:STRING, search:STRING, start:INT), INT
    'this sub searches for the LAST string search in the string
    'source, reverse of the function instr(). The sub returns 0 if
    'the search could not be found. Also this function neglects
    'content between parenthesis () in source
    INT n, bopen, bclose
    STRING sign
    
    n=start
    IF n>LEN(source) THEN n=LEN(source)-LEN(search)+1
    bopen=0     :'number of parenthesis open (
    bclose=0    :'number of parenthesis close )
    DO
        sign = MID$(source, n, LEN(search))
        'if search is found and outside parentheses then return n
        IF (sign=search) AND (bopen=bclose) THEN RETURN n
        IF LEFT$(sign,1)="(" THEN bopen++
        IF LEFT$(sign,1)=")" THEN bclose++
        n--
    UNTIL (n <= 0)
    
    'if the string search is not found, then return 0
    RETURN 0
ENDSUB

'_______________________________________________________________
SUB isOperator(expr:STRING, op:CHAR, n:INT), INT
    'This sub checks of the operator at postion n in expr is a
    'legal operator. For example the "+" in "2.3E+3" is no operator,
    'and the "-" in "3 * -2.5" is no operator but a unary minus
    STRING sign
    
    IF op="+"
        IF UCASE$(MID$(expr,n-1,1))="E"
            IF n>2
                IF INSTR("1234567890.", MID$(expr,n-2,1))>0
                    'for example "2.52E+4"
                    RETURN FALSE
                ENDIF
            ENDIF
        ENDIF
        RETURN TRUE
    ENDIF
    
    IF op="-"
        IF n=1
            'this is an unary minus, at the first position of the expr
            'for example "-3.4 / 6"
            RETURN FALSE
        ELSE
            'check for an unary minus (for example 2*-3  or  2.5E-6)
            'check the characters before the minus
            sign = LEFT$(expr,n-1)
            sign = RIGHT$(RTRIM$(sign),1)
            IF INSTR("+-/*^", sign)>0
                'For example "3.5 * -2"
                RETURN FALSE
            ENDIF
            IF UCASE$(MID$(expr,n-1,1))="E" AND n>2
                IF INSTR("1234567890.", MID$(expr,n-2,1))>0
                    'for example "2.3E-4"
                    RETURN FALSE
                ENDIF
            ENDIF
        ENDIF
        RETURN TRUE
    ENDIF
    
    'no problems found, the operator is indeed an operator.
    RETURN TRUE
ENDSUB



Copyright 2006 SpeQ Mathematics