suchen

Heim  >  Fragen und Antworten  >  Hauptteil

Javascript – Eine Algorithmusfrage im Front-End-Interview

Heute habe ich ein Vorstellungsgespräch. Ich habe keine Ahnung von Algorithmen.

Das Thema besteht darin, eine Funktion zu implementieren, die Addition, Subtraktion, Multiplikation und Division von Klammern berechnet. Die Eingabezeichenfolge ähnelt (1+2)/4+5+(3+5)*3. Können Sie das? Erklären Sie bitte ein wenig die Grundidee. Der Interviewer sagte ernst, dass dies eine Algorithmusfrage sei. Ich glaube nicht, dass es eine Implementierung von eval() sein sollte, oder?

给我你的怀抱给我你的怀抱2742 Tage vor1475

Antworte allen(11)Ich werde antworten

  • ringa_lee

    ringa_lee2017-05-19 10:29:19

    用调度场算法把中缀表达式改后缀表达式(逆波兰表达式)

    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));
    }

    Antwort
    0
  • 淡淡烟草味

    淡淡烟草味2017-05-19 10:29:19

    eval是个办法,但比较不规范,大多数情况下不要用。

    这题的正规加法二叉树运算四则表达式

    Antwort
    0
  • 仅有的幸福

    仅有的幸福2017-05-19 10:29:19

    用栈来实现表达式求值,百度下,有的

    Antwort
    0
  • 高洛峰

    高洛峰2017-05-19 10:29:19

    可以用数据结构上的逆波兰式

    Antwort
    0
  • 漂亮男人

    漂亮男人2017-05-19 10:29:19

    最通用的方法是语法分析,构建表达式树,然后求解。
    你可以自己写,也可以用一个很专业很通用的库叫Antlr。
    当然面试的时候应该是让你自己分析语法构建语法树了,真正做的时候还是Antlr更好一些。

    Antwort
    0
  • 世界只因有你

    世界只因有你2017-05-19 10:29:19

    javascript中解析四则运算表达式的算法和示例,
    楼主阔以看一哈

    javascript中解析四则运算表达式的算法和示例

    Antwort
    0
  • 巴扎黑

    巴扎黑2017-05-19 10:29:19

    我不推荐采用eval这个被抛弃的方法。一.推荐使用正则表达式 二.使用数据结构中的栈的方法
    推荐一本书:学习JavaScript数据结构与算法
    最近刚好在研究栈,队列,二叉树这些东西

    Antwort
    0
  • 漂亮男人

    漂亮男人2017-05-19 10:29:19

    这...输入字符串的话.
    你直接用eval()咯

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

    Antwort
    0
  • 巴扎黑

    巴扎黑2017-05-19 10:29:19

    解析字符串四则运算常用的是逆波兰法

    Antwort
    0
  • 大家讲道理

    大家讲道理2017-05-19 10:29:19

    用栈来实现,两年前我做数据结构实验的时候歇过一个,还带公式合法性检测呢,等我找找放哪了

    好吧,找不到了,大致印象就是要做一个二维数组来判断运算符优先级,然后计算用栈来实现

    Antwort
    0
  • StornierenAntwort