Creating a Basic Formula Editor in JavaScript

Question

I'm working on creating a basic RPG game engine prototype using JavaScript and canvas. I'm still working out some design specs on paper, and I've hit a bit of a problem I'm not quite sure how to tackle.

I will have a Character object that will have an array of Attribute objects. Attributes will look something like this:

function(name, value){
    this.name = name;
    this.value = value;
    ...
}

A Character will also have "skills" that are calculated off attributes. A skills value can also be determined by a formula entered by the user. A legit formula would look something like this:

((@attribute1Name + (@attribute2Name / 2) * 5)

where any text following the @ sign represents the name of an attribute belonging to that character. The formula will be entered into a text field as a string.

What I'm having a problem with is understanding the proper way to parse and evaluate this formula. Initially, my plan was to do a simple replace on the attribute names and eval the expression (if invalid, the eval would fail). However, this presents a problem as it would allow for JavaScript injection into the field. I'm assuming I'll need some kind of FSM similar to an infix calculator to solve this, but I'm a little rusty on my computation theory (thanks corporate world!). I'm really not asking for someone to just hand me the code so much as I'd like to get your input on what is the best solution to this problem?

EDIT: Thanks for the responses. Unfortunately life has kept me busy and I haven't tried a solution yet. Will update when I get a result (good or bad).

Answer 1

I think instead of letting them put the whole formula in, you could have select tags that have operations and values, and let them choose.

ie. a set of tags with attribute-operation-number:

<select>         <select> <input type="text">
@attribute1Name1  +        (check if input is number)
@attribute1Name2  -
@attribute1Name3  *
@attribute1Name4  /

etc.

Answer 2

There is a really simple solution: Just enter a normal JavaScript formula (i.e. as if you were writing a method for your object) and use this to reference the object you're working on.

To change this when evaluating the method use apply() or call() (see this answer).

Answer 3

I recently wrote a similar application. I probably invested far too much work, but I went the whole 9 yards and wrote both a scanner and a parser.

The scanner converted the text into a series of tokens; tokens are simple objects consisting of token type and value. For the punctuation marks, value = character, for numbers the values would be integers corresponding to the numeric value of the number, and for variables it would be (a reference to) a variable object, where that variable would be sitting in a list of objects having a name. Same variable object = same variable, natch.

The parser was a simple brute force recursive descent parser. Here's the code.

My parser does logic expressions, with AND/OR taking the place of +/-, but I think you can see the idea. There are several levels of expressions, and each tries to assemble as much of itself as it can, and calls to lower levels for parsing nested constructs. When done, my parser has generated a single Node containing a tree structure that represents the expression.

In your program, I guess you could just store that Node, as its structure will essentially represent the formula for its evaluation.

Given all that work, though, I'd understand just how tempting it would be to just cave in and use eval!

Answer 4

Different idea, hence a separate suggestion:

eval() works fine, and there's no need to re-invent the wheel.

Assuming that there's only a small and fixed number of variables in your formula language, it would be sufficient to scan your way through the expression and verify that everything you encounter is either a parenthesis, an operator or one of your variable names. I don't think there would be any way to assemble those pieces into a piece of code that could have malicious side effects on eval.

So:

• Scan the expression to verify that it draws from just a very limited vocabulary.
• Let eval() work it out.

Probably the compromise with the least amount of work and code while bringing risk down to (near?) 0. At worst, a misuser could tack parentheses on a variable name in an attempt to execute the variable.

Answer 5

I'm fascinated by the task of getting this done by the simplest means possible.

Here's another approach:

1. Convert infix to postfix;
2. use a very simple stack-based calculator to evaluate the resulting expression.

The rationale here being, once you get rid of the complication of "* before +" and parentheses, the remaining calculation is very straightforward.

Answer 6

You could look at running the user-defined code in a sandbox to prevent attacks:
http://stackoverflow.com/questions/195149/is-it-possible-to-sandbox-javascript-running-in-the-browser