Page 1 of 1
A recursive, fast and simple math evaluation.
Posted: Mon Dec 29, 2008 6:36 pm
by Mark.s
But here a fast math evaluation. Not much commented.
I will update this, if i have free time. Currently supports next operands: < + - * / > and ( )
Edit: Updated support for floats. In float numbers, need a ".". Eg like this: "22./7". But theres a alternative method too.
Edit2: Very small update.
Code: Select all
Global math.s
Global mlr3l
Global mlr3i
;A lenght for last mid.
Global Lenght = 5
Procedure.f mlr3(t=10)
If t = 10
mlr3l = Len(math)
mlr3i = 0
EndIf
n.f = 1
Repeat
c.s = Mid(math,mlr3i+1,1)
;Finds an operators
o = FindString(">*/+-()<",c,1)
If o = 5 And n.f And t
mlr3i = mlr3i + 1
;a recursive
x.f = -mlr3(0)
ElseIf o = 6
mlr3i = mlr3i + 1
x.f = ValF(Str(mlr3(9)))
ElseIf o
n.f = Pow(o, 1) + 1 ;(o / 1) + 1
If t <= n
ProcedureReturn x
EndIf
mlr3i = mlr3i + 1
If o = 7
ProcedureReturn x
EndIf
y = mlr3(n)
If o = 8
If x < y
x = 1
Else
x = 0
EndIf
ElseIf o = 5
x = x - y
ElseIf o = 4
x = x + y
ElseIf o = 3
x = x / y
ElseIf o = 2
x = x * y
ElseIf o = 1
If x > y
x = 1
Else
x = 0
EndIf
EndIf
ElseIf n
x = ValF(Mid(math,mlr3i+1,Lenght))
mlr3i = mlr3i + 1
Else
mlr3i = mlr3i + 1
EndIf
n = 0
Until mlr3i >= mlr3l
ProcedureReturn x
EndProcedure
Procedure.s Type(mlr.f)
ReturnOfType.s = ""
If FindString(math.s,".",1)
ReturnOfType=StrF(mlr.f)
Else
ReturnOfType=Str(mlr.f)
EndIf
ProcedureReturn ReturnOfType
EndProcedure
;A math
math = "(2*2)+(2*2)" ;Should be 8
OpenConsole()
PrintN(Type(mlr3()))
a.s=Input()
Alternative version of that Type procedure.s.
Code: Select all
Procedure.s Type(num.l,mlr.f)
ReturnOfType.s = ""
Select num.l
Case 1
ReturnOfType=StrF(mlr.f)
Case 2
ReturnOfType=Str(mlr.f)
EndSelect
ProcedureReturn ReturnOfType
EndProcedure
Debug Type(1,mlr3())
Re: A recursive, fast and simple math evaluation.
Posted: Mon Dec 29, 2008 9:12 pm
by PB
Doesn't work with floats (eg. 22/7 returns 3, not 3.142).
Posted: Mon Dec 29, 2008 10:42 pm
by srod
Aye it is pretty smart this.
Looks to me like you are using recursion in order to provide a way of 'stacking' operators when the question of precedence arises. Very nice.
Posted: Sun Jan 04, 2009 4:47 pm
by Froggerprogger
Very nice! But you use the expression:
x = x < y
and
x = x > y
Those are not supported by PB and should be transformed to e.g.:
Posted: Sun Jan 04, 2009 8:02 pm
by akj
Incidentally, relating to the last post, I notice that where the program has:
the middle line must be wrong as position 6 relates to '(' and not to '<' or '>'.
Posted: Sun Jan 04, 2009 8:59 pm
by Mark.s
Thanks for both, small update on example. Code should be work now right.
Demivec wrote:The code will still not produce the desired results.
Ok, and thanks, updated again.
Posted: Sun Jan 04, 2009 9:20 pm
by Demivec
Mark.s wrote:Thanks for both, small update on example. Code should be work now right.
The code will still not produce the desired results.
This portion:
Code: Select all
ElseIf o = 2
x = 1
ElseIf o = 1
x = 0
EndIf
needs to be changed to this:
Code: Select all
ElseIf o = 2
If x < y
x = 1
Else
x = 0
EndIf
ElseIf o = 1
If x > y
x = 1
Else
x = 0
EndIf
EndIf
Posted: Sat Jan 10, 2009 1:18 am
by Demivec
Mark.s wrote:But here a fast math evaluation. Not much commented.
I will update this, if i have free time. Currently supports next operands: < + - * / > and ( )
@Mark.s: thanks for this example code. The first day you posted it I added comments but before I posted I thought I would extend the code a little bit.
It is still simple but has been made easier to modify. I tried to incorporate documentation by way of using enumerations and more descriptive variable names. It has also been corrected, though most of the corrections you have also incorporated into your posting. I also removed some unnecessary bits that did not affect the results. I think it would also benefit by being modified to not use global variables but to act instead on a pointer to a expression string and also a pointer to the index for the same. I'll leave that as an exercise for those interested in doing so.
Here are some facts about my variation:
- - Operators are still limited to being represented by only a single character.
- Operators have a priority list. This makes it possible for operators to be considered "equal" for determining evaluation order.
- It supports the Operators ^, *, /, +, -, <, >, =, !, &, |, ~, (, )
- The four sets are for math, comparisons, Logical , grouping
- All logical operators and comparisons evaluate to 1 when true and 0 when false.
- The Logical operators include equivalents of And, Or, and Xor. Use parenthesis to group as desired.
- There are two Unary Operators, - and !. They can follow each other and can be repeated any number of times. For instance "---3" will equal -3 and "----3" will equal 3. Likewise "!!3" will equal 1 and "!!!3" will equal 0. You can also obtain some additional abilities by using !. Examples include "!(5 > 3)" for 5<=3, "!(5=3)" for 5<>3, etc.
- The Exponent function has been added to the math operators and also makes possible operations such as square roots by using fraction exponents (i.e. "16^0.5" equals 4).
- Numbers have the arbitrary length limit(i.e. 5 digits) removed. They can include as many digits as a float will allow.
- All expressions evaluate using floating point precision. The output can be formatted to suit ones taste by using Mark.s's Type() function or any similar function such as Round() or Int().
Code: Select all
;Math evaluation software by Mark.s
;evaluates expressions with "^*/+-!<>=&|~()"
;modifications by Demivec (Jared)
EnableExplicit
Global mathExpression.s
Global mathExpressionLength
Global mathExpressionIndex
;math operators
#MathOperatorsList$ = "^*/+-!<>=&|~()" ;operators listed in an arbitrary order
;relative priority for each respective operator in #MathOperatorsLists relative priority
#MathOperatorsPriorityValueList$ = "65544733322211" ;lowest priority = 1, a unary operator has highest priority
Enumeration
#OperatorUnmatched = 0 ;indicates operator was not found in #MathOperatorsList$
#OperatorUnary = 0 ;indicates an operator has only one operand
;the next group of operators are in the same order as in #MathOperatorsList$
#OperatorExponent
#OperatorMultiply
#OperatorDivide
#OperatorAdd
#OperatorSubtact
#OperatorLogicalNot ;unary
#OperatorLessThan
#OperatorGreaterThan
#OperatorLogicalEqual
#OperatorLogicalAnd
#OperatorLogicalOr
#OperatorLogicalXor
#OperatorLeftParen
#OperatorRightParen
;the remaining operators signal special conditions
#OperatorNewExpression
#OperatorInitExpressionEval
EndEnumeration
Procedure.f evalMathExpression(previousOperator = #OperatorInitExpressionEval)
Protected currentChar.s, isFirstOperand, operator, x.f, y.f
;uses Global mathExpression, mathExpressionLength, mathExpressionIndex
If previousOperator = #OperatorInitExpressionEval
mathExpressionLength = Len(mathExpression)
mathExpressionIndex = 0
EndIf
isFirstOperand = #True
Repeat
mathExpressionIndex + 1
currentChar.s = Mid(mathExpression, mathExpressionIndex, 1)
;attempt to identify an operator
operator = FindString(#MathOperatorsList$, currentChar, 1)
If operator = #OperatorSubtact And isFirstOperand
;perform a unary negation operation
x = -evalMathExpression(#OperatorUnary)
ElseIf operator = #OperatorLogicalNot And isFirstOperand
;perform a unary Logical Not operation
If evalMathExpression(#OperatorUnary)
x = 0
Else
x = 1
EndIf
ElseIf operator = #OperatorLeftParen
x = evalMathExpression(#OperatorNewExpression)
ElseIf operator
;check if next operator is of lower priority
If Val(Mid(#MathOperatorsPriorityValueList$,operator,1)) <= Val(Mid(#MathOperatorsPriorityValueList$,previousOperator,1))
;rollback index to previous character
mathExpressionIndex - 1
ProcedureReturn x
EndIf
If operator = #OperatorRightParen
ProcedureReturn x
EndIf
;evaluate sub-expression after operator
y = evalMathExpression(operator)
Select operator
Case #OperatorExponent
x = Pow(x,y)
Case #OperatorMultiply
x = x * y
Case #OperatorDivide
x = x / y
Case #OperatorAdd
x = x + y
Case #OperatorSubtact
x = x - y
Case #OperatorLessThan
If x < y
x = 1
Else
x = 0
EndIf
Case #OperatorGreaterThan
If x > y
x = 1
Else
x = 0
EndIf
Case #OperatorLogicalAnd
If x And y
x = 1
Else
x = 0
EndIf
Case #OperatorLogicalOr
If x Or y
x = 1
Else
x = 0
EndIf
Case #OperatorLogicalXor
If x Xor y
x = 1
Else
x = 0
EndIf
Case #OperatorLogicalEqual
If x = y
x = 1
Else
x = 0
EndIf
EndSelect
ElseIf isFirstOperand
;character is part of a new number
x = ValF(Mid(mathExpression, mathExpressionIndex))
EndIf
isFirstOperand = #False
Until mathExpressionIndex >= mathExpressionLength
ProcedureReturn x
EndProcedure
;some example
Define dummyInput.s
OpenConsole()
mathExpression = "2^3*5+(1-3)*5" ;Should be 30
PrintN( mathExpression + " = " + StrF(evalMathExpression()))
mathExpression = "(2+2)/(5*2)+(5*2)/2+2-(1*3/2)" ;Should be 5.9
PrintN( mathExpression + " = " + StrF(evalMathExpression()))
mathExpression = "(5>3)+(5<3)+!(5=3)" ;Should be 2
PrintN( mathExpression + " = " + StrF(evalMathExpression()))
mathExpression = "(5&2)*-6+!(5~3)-(0|-3)*3" ;Should be -8
PrintN( mathExpression + " = " + StrF(evalMathExpression()))
dummyInput.s = Input()
I plan to use this as a jumping off point for evaluating some expressions that are more complex. This simple and powerful example has been very helpful. Thanks again.
@Edit: source and comments edited to change the determining of operators priority. It is now possible for different operators to have equal priority. Previously each operator had its own priority. I wanted to do this before but it seemed things were working without it until Jack gave evidence to the contrary.
Posted: Sat Jan 10, 2009 9:56 am
by jack
Demivec, the code still has a bug.
try this expression "3*4+2-2*5+3", it treats it like "3*4+2-(2*5+3)" and gives 1.0 as the result, when it should be 7.0
Posted: Sat Jan 10, 2009 11:24 am
by Demivec
jack wrote:Demivec, the code still has a bug.
try this expression "3*4+2-2*5+3", it treats it like "3*4+2-(2*5+3)" and gives 1.0 as the result, when it should be 7.0
@jack: Thanks for pointing that out. I have modified the posted code to do away with that problem. With the code being commented it only took 2 minutes to make the change, though I'm sure it could be optimized.
Mark.s code also had the same evaluation problem. It was due to an operator's priority (precedence) being determined by it's sequential order in a list. This resulted in no operators being considered equal, due to the fact they would always have different sequential values. Each operator now has a value that can be set arbitrarily for determining the operator's priority in relation to another operator.
From your example, "-" and "+" can now have equal priority and will be evaluated from left to right. This also applies to other operators as well. If the priorities need to be adjusted they can be done from one place for the most part.