javascript - Soalan algoritma dalam temu bual hadapan

Question

Hari ini, saya ada temu duga pada sebelah petang Semasa temu bual kedua, ada soalan algoritma saya tidak tahu apa-apa tentang algoritma

Topiknya adalah untuk melaksanakan fungsi yang mengira operasi tambah, tolak, pendaraban dan pembahagian Rentetan input adalah serupa dengan (1+2)/4+5+(3+5)*3. Bolehkah anda terangkan serba sedikit tentang idea am? Penemubual berkata dengan bersungguh-sungguh bahawa ini adalah soalan algoritma Saya tidak fikir ia sepatutnya menjadi pelaksanaan eval(), bukan?

Answer 1

Gunakan algoritma halaman penjadualan untuk menukar ungkapan infiks menjadi ungkapan akhiran (ungkapan Poland terbalik)

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 adalah kaedah, tetapi ia agak tidak standard dan tidak boleh digunakan dalam kebanyakan kes.

Empat ungkapan biasa operasi pokok binari untuk penambahan biasa

Answer 3

Gunakan tindanan untuk melaksanakan penilaian ekspresi Di bawah Baidu, beberapa

.

Answer 4

Anda boleh menggunakan Reverse Polish pada struktur data

Answer 5

Kaedah yang paling biasa ialah analisis sintaks, membina pokok ekspresi, dan kemudian menyelesaikannya.
Anda boleh menulisnya sendiri, atau anda boleh menggunakan perpustakaan yang sangat profesional dan serba boleh dipanggil Antlr.
Sudah tentu, semasa temu duga, anda harus diminta untuk menganalisis tatabahasa dan membina pokok tatabahasa sendiri Apabila ia benar-benar melakukannya, Antlr adalah lebih baik.

Answer 6

Algoritma dan contoh menghuraikan empat ungkapan aritmetik dalam JavaScript,
Sila lihatnya

Algoritma dan contoh menghuraikan empat ungkapan aritmetik dalam JavaScript

Answer 7

Saya tidak mengesyorkan menggunakan kaedah eval yang terbengkalai. 1. Adalah disyorkan untuk menggunakan ungkapan biasa 2. Cara menggunakan tindanan dalam struktur data
Cadangkan buku: Mempelajari struktur dan algoritma data JavaScript
Saya kebetulan sedang mengkaji tindanan, baris gilir dan pokok binari baru-baru ini

Answer 8

Ini...jika anda memasukkan rentetan.
Anda boleh menggunakan eval() terus

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

Answer 9

Empat operasi aritmetik yang biasa digunakan untuk menghurai rentetan ialah kaedah Poland terbalik

Answer 10

Gunakan timbunan untuk melaksanakannya Dua tahun lalu semasa saya melakukan eksperimen struktur data, saya juga mempunyai semakan kesahihan formula. Saya akan mencari di mana untuk meletakkannya. t mencarinya. Tanggapan umum saya ialah saya ingin membuat satu. Gunakan tatasusunan dua dimensi untuk menentukan keutamaan operator, dan kemudian gunakan timbunan untuk mengiranya