Make your own free website on Tripod.com
Equation evaluator
by ericlin

The "eval" function in Javascript evaluates an equation and returns the calculation result to us. Unfortunately, the "eval" function in ActionScript is not equipped with this power. We get to build it ourselves.

The equation string need to be split and inter-pretated. This process is called "parse" and it is the basic work of a "compiler" . Although little is specific to Action script, I write this article for beginner who know nothing about "compiler".

Here is a simple movie. There are about 75 lines of scripts that parses the equation string and calculates the results. I added simple comments in the fla. The script is not difficult to understand. 

Well, instead of reading this article, you may read that script in the source fla directly.


Elements

Lets check this equation string:"abs(2^3-4*(7-2))/3+PI-pow(2,2)". In this equation, we note that operators break the equation string into several elements. The operator "/", "+" and "-" break the string into "abs(2^3-4*(7-2))", "3", "PI" and "pow(2,2)". Lets study the elements first.

There are 3 types of elements.

1. Pure numbers

String such as "23.5" is pure numbers.It is easy to get the value by Number(myString);

2. Variables

String such as "PI" is a variable name. If we try to get the value by Number("PI"), it returns NaN. To get the value, we assume that the variable names are defined in the Math class. So, the value is Math[myString].

3. Function and parenthesis

Functions elements contains parenthesis and function name in the form of "functionName(parameterString)". When functionName is null, it is a pure parenthesis. For example, "abs(2^3-4*(7-2))"  and "pow(2,2)" are functions while " (7-2)" is a pure parenthesis. 

We assume that all function names are defined in Math, so we can access the function by Math[functionName].

A function may accept more than one parameters, such as "Math.pow(2,2)".  We need to split the string in the parenthesis into param1 and param2. Although, nearly all the Math function accept at most 2 parameters, I like to make our function to accepts unknown number of parameters. Instead of using "Math[functionName](param1,param2);" I use "Math[functionName].apply(null, paramArray);" 

Of course, the parameters supplied to the Math function should be a Number not just an equation string, so we need to convert the paramString into a numeric value. This is achieved through recursive call of the "evaluate" function itself.


Operators

For an equation string as "3+4", we split it by operator "+" into left part "3" and right part "4". Then according to the operator, we handle the left part and right part.  In this example, the operator is "+", so the script will return the result by "Add". We write a large block of script to handle this job. Basically this is done through a "switch (operator)" block.

Lets check this equation string: "5+4/2*3";  The result is 11.  Please note the sequence we pick the operator. We first calculate (4 divided by 2) and then calculate (4/2 multiply with 3)  and the last is to calculate (5 add with 4/2*3).    

We get the first rule about sequence of parsing operator. Some operator such as "*","/" and "^" has the priority to be calculated earlier than other operator such as "+" and "-"; When we do parsing, the operator with lower priority get parsed first.

Something must be clarified here. Let's  check this equation string: "10-5*-3". Here we see two "-" operator here. In fact, the first one is "subtraction" but the second one is "negative sign". The "subtraction" operator has lower priority than "multiply" while the "negative sign" has very high priority. So, the calculation is (-3) and then 5*(-3) and then 10-(5*(-3)). For this reason, my operation include twice the "addition" and "subtraction".

Lets check another equation string : "18/6/3". The result is 1 not 9. We do the calculation from left to right. So, our second rule about calculation priority is "left to right". That means, we need to parse the operator in the contradictory way, from right to left.


Parenthesis

Before parse operators, we need to mask the parenthesis.

Check this equation string :"1-(2*(3+4))/(5-6)-7". If we parse this string directly with the operator "+", we might well split it in the middle of the parenthesis and get two wrong elements with un-paired parenthesis bracket : "1-(2*(3"  and "4))/(5-6)-7".

To correct this, before we start to parse the "+" operator, we need to mask off the "first level parenthesis".  The resulted string  should be  "1-($$$$$$$$)/($$$)-7";  The characters embraced in each first level parenthesis should be masked and spared from parsing. Those strings will be isolated out as in-dependant equation strings "2*(3/4)" and "5-6";

So, when we meet the first level left bracket "(" , how to we know which right bracket ")" is the matched one ? There is no short way. It is not the first ")" met nor the last ")". We need to walk through each character and "count" how deep we are in and out for a match.


The recursive function

To get the value of equation "3*4+5*6", we add up two values. One is the value of equation "3*4" and the other is the value of equation "5*6". To get the value of these resulted equations we call the function itself to evaluate. 

The call starts from operator with lower priority and the return comes back in backward order. So, the operator "+" calls the recursive function which handle the "*" operator. And, the return starts from "*" back to "+".

Although Flash allows only 256 recursive stack, I believe it is far enough to handle usual equations.


Extend the support

1. Custom variables 

In this simple evaluator, we assume our variables are all defined in Math class. So, we can calculate "PI" or "LN10" ... etc. What about custom variables ? For example, we have set x=3, we should be able to evaluate an equation : "x^2+x+1" to get the result as 13. We need this function if we want to make "equation grapher". 

It is not difficult. We may create a variable pool to hold these variable names. When the variable name is not found in Math class, search there for it.

2. Custom functions

We have assumed that our functionName are all defined in Math class. What if we want some function as "sec" - the inverse of cos or "cot" the inverse of tan ? Or, we may want some custom functions such as "getMortgage", "getInterestRate" or "getFactorial" ... etc. 

Likewise, we add those functionNames to the variable pool and define the detail of those functions.

3. Custom operators

At present it supports only 5 operators : "+-*/^".  We may add other operators such as ">", "<" ,"&","|" or "!" (define it as "NOT" or "Factorial"). We need to include those operators in the operatorSet array. Be careful, which position it should be put at is very important because the order is arranged with priority. We also need to extend our "switch" block to handle those operators.

4. Actionscript Inter-pretator

Can we evaluate a string such as "_root.mc._rotation=(180/PI)*atan2(3,4);" to make a movieClip rotate ?

Sure! We add an operator "=" for parse. We use "eval" to get the reference of left side string and assign the evaluated result of right side string to it.

It is not difficult to handle the string in this example. But, to generalize the power to accept all syntax in ActionScript is not an easy work.  Someone has tried a limited "actionscript interpretator" to translate "actionscript string" into action. I dont want to try it. 


The script

operatorSet = "+-*/^+-";
// The sequence of operator in this operatorSet array is important
_global.evaluate = function(str) {
	str = str.split(" ").join("");
	//trim off the space if any
	if (!str.length>0) {
		return 0;
	}
	// search for  +,-,*,/,*    , skip string in parenthesis and cut into two pieces accordingly
	// after this step ,  only function, parenthesis, variable or number are  left
	var str2 = maskParenthesis(str);
	for (var k = 0; k<operatorSet.length; k++) {
		var op = operatorSet.charAt(k);
		// becareful, we should check from right to left, not left to right
		var op = operatorSet.charAt(k);
		var start = str.length-1;
		var i = 0;
		while ((i=str2.lastIndexOf(op, start))>=0) {
			if ((k<=1) && operatorSet.indexOf(str2.charAt(i-1))>=0) {
				//something like 3*-4;  
				start = i-1;
				//################continue
				continue;
			}
			var lStr = str.substr(0, i);
			var rStr = str.substr(i+1, str.length-i-1);
			return handleOperator(op, lStr, rStr);
		}
	}
	// now we get only the parenthesis, function and pure number/variable here; now check function
	var start = str.indexOf("(");
	if (start>=0) {
		var functionName = (str.substr(0, start)).toLowerCase();
		var contentInParenthesis = str.substr(start+1, str.length-start-2);
		return handleFunction(functionName, contentInParenthesis);
	}
	// After those steps , only variable and pure number are left here, now check variable
	if (isNaN(str)) {
		return Math[str];
	}
	// variable are screened off, here is pure value
	return Number(str);
};
// ####################################
function handleOperator(operator, lStr, rStr) {
	var num1 = evaluate(lStr);
	var num2 = evaluate(rStr);
	switch (operator) {
	case "+" :
		return num1+num2;
	case "-" :
		return num1-num2;
	case "*" :
		return num1*num2;
	case "/" :
		return num1/num2;
	case "^" :
		return Math.pow(num1, num2);
	default :
		return (trace("unknown operator="+opChar));
	}
}
// ###############################################################
function handleFunction(functionName, contentInParenthesis) {
	if (!functionName.length>0) {
		// pure parenthesis
		return evaluate(contentInParenthesis);
	}
	// It is a function, now check how many parameters
	var str2 = maskParenthesis(contentInParenthesis);
	var str = contentInParenthesis;
	var params = [];
	var i = -1;
	while (i=str2.indexOf(",")>=0) {
		var lStr = str.substr(0, i);
		var str2 = str2.substr(i+1, str2.length-i-1);
		var str = str.substr(i+1, str.length-i-1);
		params.push(evaluate(lStr));
	}
	params.push(evaluate(str));
	return Math[functionName].apply(null, params);
}
// -------------------------------------------------------------------------
function maskParenthesis(str) {
	// skip the first level parenthesis
	var parenthesisStack = 0;
	var temp = "";
	for (var i = 0; i<str.length; i++) {
		var char = str.substr(i, 1);
		if (char == "(") {
			parenthesisStack++;
		}
		if (char == ")") {
			parenthesisStack--;
		}
		temp += (parenthesisStack == 0 ? char : "(");
	}
	if (parenthesisStack != 0) {
		trace("parenthesis not match");
		return "";
	}
	return temp;
}

download source file

ericlin@ms1.hinet.net