scan string operators - javascript

Question

In a calculator I own 4 input type ="number" in particular:

<input type = "number" id ="mol" min="1" max="4">
<input type = "number" id ="div" min="1" max="4">
<input type = "number" id ="add" min="1" max="4">
<input type = "number" id ="min" min="1" max="4">

In a textbox, I insert the mathematical expression for extended.

<input type = "text" id = "exp" readonly>

The numerical values ​​and the operators have gone through the normal buttons. So, for example, the expression inserted in the textbox is this: 8*5-9/2+3

Now I would want that when I press the equal key, based on the priority that the customer has given to the operands, the expression result changed.

multiplication: 1
division: 4
subtraction: 2
addition: 3

-> 40 - 9 / 2 + 3
-> 31 / 2 + 3
-> 31 / 5
-> = 6.2

I think this is very difficult to achieve. Get the value of the textbox and evaluate the result based on the priority of the operands is really extreme. What do you propose?

Answer 1

Try using the split method: http://msdn.microsoft.com/en-us/library/t5az126b(v=vs.94).aspx

Split on the operator with the first priority first, then split each group by the second operator, then for each subgroup split by the third operator, and for each of those sub-subgroups split by the fourth. Then apply the operator to the groups moving upward.

Conceptual example (not the full code you'll need, but should give an idea):

var expression = "8*5-9/2+3"; // Get this from the data
var operator1Groups = expression.split("*"); // Instead of hardcoding this, retrieve which operator has highest priority from the data
for (var i in operator1Groups) {
    var operator2Groups = operator1Groups[i].split("+"); // Similarly, don't hardcode the operator
    // And so on...
    // Once you get to the lowest operator, start applying the operator to each group
}

Answer 2

The way to do this is with an Operator Precedence Parser. They are commonly implemented using Djikstra's Shunting-yard Algorithm. You could specify the precedence by loading the operators and precedences into a list and then running the algorithm:

function parse(inputExpression, operators) {
    // Strip out anything that isn't a number or a math operator
    var tokens = inputExpression
                .replace(/[^0-9+\-*\/()]/g, '')
                .split(/([+\-*\/()])/)
                .filter(function(x) { return x != ""; });

    var outputQ = []; // push = push, pop = pop
    var operStk = []; // enqueue = push, dequeue = shift

    function top(stack) { return stack[stack.length-1]; }

    while(tokens.length !== 0) {
        var token = tokens.shift();
        if(!isNaN(Number(token))) {
            outputQ.push(token);
        } else if (operators.hasOwnProperty(token)) {
            while(operators[token] >= operators[top(operStk)])
                outputQ.push(operStk.pop());
            operStk.push(token);
        } else if (token == '(') {
            operStk.push(token);
        } else if (token == ')') {
            while(top(operStk) != '(' && operStk.length != 0)
                outputQ.push(operStk.pop());

            if(operStk.length == 0)
                return null;

            operStk.pop(); // Get rid of the l-paren
        } else {
            console.log("Bad token '" + token + "'");
            return null;
        }
    }

    while(operStk.length > 0) 
        outputQ.push(operStk.pop());

    return outputQ;
}

function evaluate(parseResult) {
    if (parseResult === null) return null;

    var valueStack = [];
    while(parseResult.length !== 0) {
        var op = parseResult.shift();
        if(!isNaN(Number(op)))
            valueStack.push(Number(op));
        else {
            var val2 = valueStack.pop();
            var val1 = valueStack.pop();
            if(op == '+') {
                valueStack.push(val1 + val2);
            } else if(op == '-') {
                valueStack.push(val1 - val2);
            } else if(op == '*') {
                valueStack.push(val1 * val2);
            } else if(op == '/') {
                valueStack.push(val1 / val2);
            } else {
                console.log("Invalid operator '" + op + "'");
                return null;
            }
        }
    }

    if(valueStack.length !== 1) {
        console.log("Invalid stack. Remaining: " + valueStack);
        return null;
    }

    return valueStack.pop();
}

Usage:

var operators = {
    "+": 3,
    "-": 2,
    "*": 1,
    "/": 4
};
evaluate(parse("40 - 9 / 2 + 3", operators)); // == 6.2

Note that this will not handle unary minus, because it's difficult to do with Shunting-yard, and because you aren't asking for a precedence for it. On the bright side, it does support parenthesis.

Hope this helps!

Alex