Javascript – Eine Algorithmusfrage im Front-End-Interview

Question

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?

Answer 1

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

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是个办法，但比较不规范，大多数情况下不要用。

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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