javascript - An algorithm question in front-end interview

Question

Today, there is an interview in the afternoon. During the second interview, there was an algorithm question. I don’t know anything about algorithms. Please ask someone to help me.

The topic is to implement a function for calculating addition, subtraction, multiplication and division of parentheses. The input string is similar to (1 2)/4 5 (3 5)*3. Similar legal operations
Can you explain the general idea a little bit? The interviewer said earnestly that this was an algorithm question. I don’t think it should be an implementation of eval(), right?

Answer 1

Use the dispatching field algorithm to change the infix expression into a suffix expression (reverse Polish expression)

var A = '((112 + 2) * (32 + (43 + 45 - 46) * 12))';

function is_op(val) {
    var op_string = '+-*/()';
    return op_string.indexOf(val) > -1;
}

function init_expression(expression) {
    var expression = expression.replace(/\s/g, ''),
        input_stack = [];
    input_stack.push(expression[0]);
    for (var i = 1; l = expression.length, i<l; i++) {
        if (is_op(expression[i]) || is_op(input_stack.slice(-1))) {
            input_stack.push(expression[i]);
        } else {
            input_stack.push(input_stack.pop()+expression[i]);
        }
    }
    return input_stack;
}

function op_level (op) {
    if (op == '+' || op == '-') {
        return 0;
    }
    if (op == '*' || op == '/') {
        return 1;
    }
    if (op == '(') {
        return 3;
    }
    if (op == ')') {
        return 4;
    }
}

function RPN (input_stack) {
    var out_stack = [], op_stack = [], match = false, tmp_op;
    while (input_stack.length > 0 ) {
        var sign = input_stack.shift();
        if (!is_op(sign)) {
            out_stack.push(sign);
        } else if (op_level(sign) == 4) {
            match = false;
            while (op_stack.length > 0 ) {
                tmp_op = op_stack.pop();
                if ( tmp_op == '(') {
                    match = true;
                    break;
                } else {
                    out_stack.push(tmp_op);
                }
            } 
            if (match == false) {
                return 'lack left';
            }
        } else {
            while ( op_stack.length > 0 && op_stack.slice(-1) != '(' && op_level(sign) <= op_level(op_stack.slice(-1))) {
                out_stack.push(op_stack.pop());
            }
            op_stack.push(sign);   
        }
    }
    while (op_stack.length > 0 ){
        var tmp_op = op_stack.pop();
        if (tmp_op != '(') {
            out_stack.push(tmp_op);
        } else {
            return 'lack right';
        }
    }
    return out_stack;
}

function cal(expression) {
    var i, j, 
        RPN_exp = [],
        ans;
    while (expression.length > 0) {
        var sign = expression.shift();
        if (!is_op(sign)) {
            RPN_exp.push(sign);
        } else {
            j = parseFloat(RPN_exp.pop());
            i = parseFloat(RPN_exp.pop());
            RPN_exp.push(cal_two(i, j, sign));
        }
    }
    return RPN_exp[0];
}

function cal_two(i, j, sign) {
    switch (sign) {
        case '+':
            return i + j;
            break;
        case '-':
            return i - j;
            break;
        case '*':
            return i * j;
            break;
        case '/':
            return i / j;
            break;
        default:
            return false;
    }
}


var expression = RPN(init_expression(A))
if (expression == 'lack left' || expression == 'lack right') {
    console.log(expression);
} else {
    console.log(cal(expression));
}

Answer 2

eval is a method, but it is relatively unstandardized and should not be used in most cases.

The four expressions of regular addition binary tree operation for this question

Answer 3

Use the stack to implement expression evaluation. On Baidu, there are some

Answer 4

You can use reverse Polish on data structure

Answer 5

The most common method is syntax analysis, building an expression tree, and then solving it.
You can write it yourself, or you can use a very professional and versatile library called Antlr.
Of course, during the interview, you should be asked to analyze the grammar and build the grammar tree yourself. When it comes to actually doing it, Antlr is better.

Answer 6

Algorithms and examples of parsing four arithmetic expressions in JavaScript,
Please take a look at it

Algorithms and examples of parsing four arithmetic expressions in JavaScript

Answer 7

I don’t recommend using the abandoned method of eval. 1. It is recommended to use regular expressions 2. How to use stacks in data structures
Recommend a book: Learning JavaScript data structures and algorithms
I just happened to be studying things like stacks, queues, and binary trees recently

Answer 8

This...if you input a string.
You can use eval() directly

var a = '(1+2)/4+5+(3+5)*3';
eval(a);

Answer 9

The commonly used method of parsing the four arithmetic operations of strings is the reverse Polish method

Answer 10

Use a stack to implement it. Two years ago when I was doing data structure experiments, I had one. It also had a formula legality check. I’m going to look for where to put it.

Okay, I can’t find it. My general impression is that I want to make one. Use a two-dimensional array to determine the operator priority, and then use the stack to calculate it