Expression Evaluator
Simple expresion evaluator that transforms infix expressions into postfix and then evaluates them. Also features a function that optimises postfix expressions by trying to remove redundant operations and evaluating constant numerics as much as possible.
ActionScript3 source code
/**
* Copyright Luiz ( http://wonderfl.net/user/Luiz )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/eKzf
*/
package
{
import flash.events.*;
import flash.text.*;
import flash.display.Sprite;
public class FlashTest extends Sprite
{
public var f:TextField;
public var output:TextField;
public var evalBtn:Sprite;
public function FlashTest()
{
// write as3 code here..
var txtFormat:TextFormat = new TextFormat();
txtFormat.font = "Courier New";
txtFormat.size = 13;
txtFormat.color = 0;
// Create the textfield
f = new TextField();
f.x = 10;
f.y = 10;
f.defaultTextFormat = txtFormat;
f.setTextFormat(txtFormat);
f.text = "sin!(pi / 2) * log!(e * 10)";
f.width = stage.stageWidth - 11;
f.height = 170;
f.type = TextFieldType.INPUT;
f.border = true;
addChild(f);
// Create the eval button
evalBtn = new Sprite();
evalBtn.x = 10;
evalBtn.y = 190;
evalBtn.graphics.beginFill(0x009966, 1);
evalBtn.graphics.drawRect(0, 0, 170, 30);
evalBtn.buttonMode = true;
evalBtn.useHandCursor = true;
// Add the Evan button label
var label:TextField = new TextField();
label.text = "Evaluate expression";
label.autoSize = "left";
label.x = 5;
label.y = 5;
label.setTextFormat(txtFormat);
label.mouseEnabled = false;
label.textColor = 0xFFFFFF;
evalBtn.addChild(label);
addChild(evalBtn);
// Create the output textfield
output = new TextField();
output.x = 10;
output.y = 230;
output.defaultTextFormat = txtFormat;
output.setTextFormat(txtFormat);
output.text = "Output appears here";
output.width = stage.stageWidth - 11;
output.height = 170;
output.border = true;
addChild(output);
// Prepare the functions array
var funcs:Array = [];
funcs.push("sin", Math.sin);
funcs.push("cos", Math.cos);
funcs.push("atan", Math.atan);
funcs.push("round", Math.round);
funcs.push("floor", Math.floor);
funcs.push("ceil", Math.ceil);
funcs.push("abs", Math.abs);
funcs.push("sqrt", Math.sqrt);
funcs.push("log", Math.log);
funcs.push("acos", Math.acos);
funcs.push("asin", Math.asin);
funcs.push("log", Math.log);
funcs.push("sign", function(x:Number) : Number { return (x < 0 ? -1 : (x > 0 ? 1 : 0)); });
// Prepare the variables array
var vars:Array = [];
vars.push("pi", Math.PI);
vars.push("e", Math.E);
// Add the event listeners
evalBtn.addEventListener(MouseEvent.CLICK,
function (e:Event) : void
{
try
{
var out:String = "";
out += "Output: " + eval(f.text, vars, funcs) + "\n";
out += "Postfix: " + toPostfix(f.text) + "\n";
out += "Optimized Postfix: " + optimisePostfix(toPostfix(f.text));
output.text = out;
}
catch(e:Error)
{
output.text = e.toString();
}
}
);
}
// Evaluates a string expression
public static function eval(exp:String, vars:Array = null, func:Array = null) : *
{
// Convert the expression into a postfix expression
var postfix:String = toPostfix(exp);
return evalPostfix(postfix, vars, func);
}
// Evaluats a postfix string expression
public static function evalPostfix(postfix:String, vars:Array = null, func:Array = null) : *
{
// Evaluate the postfix string
var stack:Vector.<*> = new Vector.<*>();
var returnValue:* = 0;
var cur:String = "";
var c:String;
var l:int = postfix.length;
for(var i:int = 0; i < l; i++)
{
c = postfix.charAt(i);
// Space
if(c == " ")
{
if(cur != "")
{
// Push the current token to the stack
stack.push(tryNumConvert(cur));
}
cur = "";
}
// Alphanumeric digit
else if(c != " " && (isAlphanumeric(c) || c == "."))
{
cur += c;
}
// Operator
else if(isOperator(c))
{
var value1:*;
var value2:*;
var retVal:*;
// Check for the unary minus sign
if(c == "-")
{
if(i < postfix.length)
{
// Try to capture all numbers in front of the '-' sign to turn into a valid number
if(isDigit(postfix.charAt(i+1)))
{
var digitIndex:int = i + 1;
var digitString:String = "";
var numString:String = "";
// While the current digit is a '.' symbol or a number, keep adding it to the digit string
while((digitString = postfix.charAt(digitIndex)) == "." || isDigit(digitString))
{
numString += digitString;
digitIndex++;
}
// Conver the number to the stack
stack.push(-tryNumConvert(numString));
// Jump the characters that were skipped
i = digitIndex;
continue;
}
}
}
// Unary negation operator
else if(c == "@")
{
value1 = stack.pop();
stack.push(-value1);
continue;
}
// Pop two values from the stack
value1 = stack.pop();
value2 = stack.pop();
// Assign values to the variables if it's a string
if(!isDigit(value1))
{
if(value1 == "NInfinity")
{
value1 = Number.NEGATIVE_INFINITY;
}
else if(value1 == "NaN")
{
value1 = Number.NaN;
}
else if(vars == null || vars.indexOf(value1) == -1)
{
throw new Error("Variable " + value1 + " was not declared");
}
else
{
value1 = vars[vars.indexOf(value1) + 1];
}
}
// Assign values to the variables if it's a string
if(!isDigit(value2))
{
// Function call
if(c == "!")
{
if(func == null || func.indexOf(value2) == -1)
{
throw new Error("Function " + value2 + " was not declared");
}
}
// Variable
else
{
if(value2 == "NInfinity")
{
value2 = Number.NEGATIVE_INFINITY;
}
else if(value2 == "NaN")
{
value2 = Number.NaN;
}
else if(vars == null || vars.indexOf(value2) == -1)
{
throw new Error("Variable " + value2 + " was not declared");
}
else
{
value2 = vars[vars.indexOf(value2) + 1];
}
}
}
if(!(value1 is Number))
value1 = tryNumConvert(value1);
if(!(value1 is Number))
value2 = tryNumConvert(value2);
// Evaluate the operation
switch(c)
{
case "+":
retVal = value2 + value1;
break;
case "-":
retVal = value2 - value1;
break;
case "*":
retVal = value2 * value1;
break;
case "/":
retVal = value2 / value1;
break;
case "&":
retVal = value2 & value1;
break;
case "|":
retVal = value2 | value1;
break;
case "^":
retVal = value2 ^ value1;
break;
case "%":
retVal = value2 % value1;
break;
case "!":
retVal = func[func.indexOf(value2) + 1].call(null, value1);
break;
}
stack.push(retVal);
}
}
// If the expression has only one value, evaluate it and push it to the stack
if(cur != "")
{
value1 = cur;
// Assign variables to the values if it's a string
if(!isDigit(value1))
{
if(value1 == "NInfinity")
{
value1 = Number.NEGATIVE_INFINITY;
}
else if(value1 == "NaN")
{
value1 = Number.NaN;
}
else if(vars == null || vars.indexOf(value1) == -1)
{
throw new Error("Variable " + value1 + " was not declared");
}
else
{
value1 = vars[vars.indexOf(value1) + 1];
}
}
stack.push(value1);
}
return stack.pop();
}
// Convers an infix expression to postfix
public static function toPostfix(infix:String) : String
{
var postfix:String = "";
var stack:Vector.<String> = new Vector.<String>();
stack.push("(");
// Whether to read the next operator as an unary operator
var unary:Boolean = true;
var l:int = infix.length;
for(var i:int = 0; i < l; i++)
{
var current:String = infix.charAt(i);
if (current == " ")
{
// ignore
}
// If it's a digit or '.' or a letter ("variables"), add it to the output
else if(isAlphanumeric(current) || current == ".")
{
postfix += current;
// Disable unary processing
unary = false;
}
else if(current == "(")
{
stack.push(current);
// Disable unary processing
unary = true;
}
else if(isOperator(current))
{
var rightOperator:String = current;
// Check for the unary minus sign
if(current == "-" && unary)
{
rightOperator = "@";
}
while((stack.length > 0) && isOperator(stack[stack.length - 1]) && precedence(stack[stack.length - 1], rightOperator))
{
postfix += " " + stack.pop();
}
postfix += " ";
stack.push(rightOperator);
unary = true;
}
// We've hit a right parens
else if(current == ")")
{
// While top of stack is not a left parens
while((stack.length > 0) && stack[stack.length - 1] != "(")
{
postfix += " " + stack.pop();
}
if (stack.length == 0)
{
throw new Error("Missing left parenthesis on expression");
}
// Discard the left paren
stack.pop();
// Disable unary processing
unary = false;
}
}
// Started with a left paren, now close it:
// While top of stack is not a left paren
while((stack.length > 0) && stack[stack.length - 1] != "(")
{
postfix += " " + stack.pop();
}
if (stack.length == 0)
{
throw new Error("Missing left parenthesis on expression");
}
// Discard the left paren
stack.pop();
// all open parens should be closed now -> empty stack
if (stack.length > 0)
{
throw new Error("missing right parenthesis on expression");
}
return postfix;
}
// Optimises a postfix string expression by inlining constant calculations
public static function optimisePostfix(postfix:String) : String
{
var symbolsStack:Vector.<Object> = new Vector.<Object>();
var curSymbol:String = "";
var c:String = "";
var l:int = postfix.length;
for(var i:int = 0; i < l; i++)
{
c = postfix.charAt(i);
if(c == " ")
{
symbolsStack.push(tryNumConvert(curSymbol));
curSymbol = "";
}
else
{
// Check for the unary minus sign
if(c == "-")
{
if(i < postfix.length)
{
// Try to capture all numbers in front of the '-' sign to turn into a valid number
if(isDigit(postfix.charAt(i+1)))
{
var digitIndex:int = i + 1;
var digitString:String = "";
var numString:String = "";
// While the current digit is a '.' symbol or a number, keep adding it to the digit string
while((digitString = postfix.charAt(digitIndex)) == "." || isDigit(digitString))
{
numString += digitString;
digitIndex++;
}
// Conver the number to the stack
symbolsStack.push(-tryNumConvert(numString));
// Jump the characters that were skipped
i = digitIndex;
continue;
}
}
}
curSymbol += c;
}
}
if(curSymbol != "")
{
symbolsStack.push(curSymbol);
}
var symbol:*;
var value1:* = null;
var value2:* = null;
var lastOperator:String = "";
// Iterate through the symbols stack
for(i = 0; i < symbolsStack.length; i++)
{
symbol = symbolsStack[i];
if(isOperator(symbol))
{
var operator:String = symbol;
var retVal:*;
value2 = symbolsStack[i-1];
value1 = symbolsStack[i-2];
// Remove '+ 0's and '- 0's from the expression
if((operator == "+" || operator == "-") && symbolsStack[i-1] == 0)
{
symbolsStack.splice(i - 1, 2);
i -= 1;
continue;
}
// Deal with unary operators
if(operator == "-" && i == 0)
{
return parseFloat(postfix) + "";
break;
}
if(isOperator(value1) || isOperator(value2))
continue;
// Skip if value is a variable or function
if(!(value1 is Number && !isNaN(value1)) || !(value2 is Number && !isNaN(value2)))
{
// Optimize multiplication and division by 1 and multiplication by 0
if(operator == "*" || operator == "/")
{
// If there's a division by 0, retain the expression so it can be evaluated bellow
if(value2 == 0 && operator == "/") { }
// Remove multiplication by 1
else if(operator == "*" && value1 == 1)
{
symbolsStack.splice(i - 2, 3, value2);
i -= 2;
value2 = value2;
value1 = symbolsStack[i];
continue;
}
// Remove multiplication by 1
else if(operator == "*" && value2 == 1)
{
symbolsStack.splice(i - 2, 3, value1);
i -= 2;
value2 = value1;
value1 = symbolsStack[i];
continue;
}
// Remove multiplication by 0
else if(value1 == 0 && operator == "*" && !isNaN(value2))
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
// Remove multiplication by 0
else if(value2 == 0 && operator == "*" && !isNaN(value2))
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
// Remove divisions where the left hand value is 0
else if(value1 == 0 && operator == "/" && !isNaN(value2))
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
}
// Optimize sum and subtraction
else if(operator == "+" || operator == "-")
{
// Remove sums and subtractions with a 0 right param
if(value2 == 0)
{
symbolsStack.splice(i - 2, 3, value1);
i -= 2;
value2 = value1;
value1 = symbolsStack[i];
continue;
}
// Remove subtractions of two equal values that will always result in 0
else if(value1 == value2 && operator == "-")
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
}
// Optimize the two first bitwise operations
else if(operator == "&" || operator == "|")
{
// Remove bitwise 'and's and 'or's of two equal values that will always result in the same value
/*if(value1 == value2)
{
symbolsStack.splice(i - 2, 3, value2);
i -= 2;
value1 = symbolsStack[i];
continue;
}*/
// Remove 'and' operations with 0
if(operator == "&" && (value1 == 0 || value2 == 0))
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
}
// Optimize the extra bitwise operation
else if(operator == "^")
{
// Remove bitwise 'not's of two equal values that will always result in the 0
if(value1 == value2)
{
symbolsStack.splice(i - 2, 3, 0);
i -= 2;
value2 = 0;
value1 = symbolsStack[i];
continue;
}
}
// Unary '-' operator
else if(operator == "@")
{
if(value2 is Number)
{
symbolsStack.splice(i - 1, 2, -value2);
}
continue;
}
continue;
}
// Evaluate the operation
switch(operator)
{
case "+":
retVal = value1 + value2;
break;
case "-":
retVal = value1 - value2;
break;
case "*":
retVal = value1 * value2;
break;
case "/":
retVal = value1 / value2;
break;
case "&":
retVal = value1 & value2;
break;
case "|":
retVal = value1 | value2;
break;
case "^":
retVal = value1 ^ value2;
break;
case "%":
retVal = value1 % value2;
break;
}
if(retVal == Number.NEGATIVE_INFINITY)
retVal = "NInfinity";
// Pop the operator and both values and place the result in the stack
symbolsStack.splice(i - 2, 3, retVal);
i -= 2;
value2 = value1;
value1 = symbolsStack[i];
}
else
{
value2 = value1;
value1 = symbolsStack[i];
}
}
return symbolsStack.join(" ");
}
// Tries to optimize a postfix expression into a single value, returning an expression if it fails
public static function tryOptimisePostfixToValue(postfix:String) : *
{
var exp:String = optimisePostfix(postfix);
return tryNumConvert(exp);
}
// Returns whether the given character is an operator
public static function isOperator(char:String) : Boolean
{
switch (char)
{
case "@":
case "+":
case "-":
case "*":
case "/":
case "^":
case "&":
case "|":
case "^":
case "%":
case "!":
return true;
default:
return false;
}
}
// returns whether a `lOp` b `rOp` c == (a `lOp` b) `rOp` c
public static function precedence(leftOperator:String, rightOperator:String) : Boolean
{
// Function call
if(leftOperator == "!")
{
return true;
}
else if(rightOperator == "!")
{
return false;
}
// Unary minus
else if(leftOperator == "@")
{
return true;
}
else if(rightOperator == "@")
{
return false;
}
// Multiplication, division and modulo
else if(leftOperator == "*" || leftOperator == "/" || leftOperator == "%")
{
return true;
}
else if(rightOperator == "*" || rightOperator == "/" || rightOperator == "%")
{
return false;
}
// Sum and subtraction
else if(leftOperator == "+" || leftOperator == "-")
{
return true;
}
else if(rightOperator == "+" || rightOperator == "-")
{
return false;
}
// Bitwise operator
else if(leftOperator == "&" || leftOperator == "^")
{
return true;
}
else if(rightOperator == "&" || rightOperator == "^")
{
return false;
}
// Rest of the bitwise operators
else if(leftOperator == "|")
{
return true;
}
else if(rightOperator == "|")
{
return false;
}
return true;
}
// Tries to conver a string value into a numeric value
// If the string is not a valid numeric value, it returns a string
public static function tryNumConvert(str:*) : *
{
if(str is Number)
return str;
var num:Number = parseFloat(str);
return (isNaN(num) ? str : num);
}
// Returns whether the given string is alphanumeric
public static function isAlphanumeric(str:String) : Boolean
{
var c:int = str.charCodeAt(0);
// a -- z A -- Z 0 -- 9
return ((c >= 65 && c <= 90) || (c >= 97 && c <= 122) || (c >= 48 && c <= 57));
}
// Returns whether the given string is a number
public static function isDigit(str:*) : Boolean
{
if(str is Number)
return true;
return !isNaN(parseFloat(str));
}
}
}