javascript - Une question d'algorithme lors d'un entretien frontal

Question

Aujourd'hui, j'ai un entretien dans l'après-midi. Lors du deuxième entretien, il y a eu une question sur les algorithmes. Je ne connais rien aux algorithmes. Veuillez demander à quelqu'un de m'aider.

Le sujet est d'implémenter une fonction qui calcule l'addition, la soustraction, la multiplication et la division des parenthèses. La chaîne d'entrée est similaire à (1+2)/4+5+(3+5)*3. expliquer un peu l'idée générale ? L'intervieweur a dit sincèrement qu'il s'agissait d'une question d'algorithme. Je ne pense pas que cela devrait être une implémentation de eval(), n'est-ce pas ?

Answer 1

Utilisez l'algorithme du dispatching pour changer l'expression infixe en expression suffixe (expression polonaise inversée)

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 est une méthode, mais elle est relativement non standardisée et ne doit pas être utilisée dans la plupart des cas.

Les quatre expressions régulières de l'opération d'arbre binaire pour l'addition régulière

Answer 3

Utilisez la pile pour implémenter l'évaluation d'expression. Sur Baidu, il y en a

.

Answer 4

Vous pouvez utiliser le style polonais inversé de la structure des données

Answer 5

La méthode la plus courante est l'analyse syntaxique, la construction d'un arbre d'expression, puis sa résolution.
Vous pouvez l'écrire vous-même ou utiliser une bibliothèque très professionnelle et polyvalente appelée Antlr.
Bien sûr, lors de l'entretien, il devrait vous être demandé d'analyser la grammaire et de construire vous-même l'arbre grammatical. Quand il s'agit de le faire, Antlr est meilleur.

Answer 6

Algorithmes et exemples d'analyse de quatre expressions arithmétiques en javascript,
L'affiche originale a un bon look

Algorithmes et exemples d'analyse de quatre expressions arithmétiques en javascript

Answer 7

Je ne recommande pas d'utiliser la méthode d'évaluation abandonnée. 1. Il est recommandé d'utiliser des expressions régulières 2. Comment utiliser les piles dans les structures de données
Recommander un livre : Apprendre les structures de données et les algorithmes JavaScript
J'ai récemment étudié des choses comme les piles, les files d'attente et les arbres binaires

Answer 8

Ceci... si vous saisissez une chaîne.
Vous pouvez utiliser eval() directement

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

Answer 9

La méthode couramment utilisée pour analyser les quatre opérations arithmétiques des chaînes est la méthode polonaise inverse

Answer 10

Utilisez une pile pour l'implémenter. Il y a deux ans, lorsque je faisais des expériences sur la structure des données, j'en avais une qui vérifiait également la légalité de la formule.

D'accord, je peux. Je ne le trouve pas. Mon impression générale est que je veux en créer un. Utilisez un tableau bidimensionnel pour déterminer la priorité de l'opérateur, puis utilisez la pile pour la calculer

.