javascript - 前端面試的一道演算法題

Question

今天，下午有一個面試，二面的時候有道算法題，我對演算法一竅不通，求大神解惑

題目是 實現計算加減乘除括號運算的函數 輸入字串 類似 (1 2)/4 5 (3 5)*3 類似的合法運算
能不能稍微講解下大體思路是什麼？面試大哥當時語重心長的說了聲這是演算法題，我想不應該是eval()這種實作吧？

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

用棧來實現,兩年前我做數據結構實驗的時候歇過一個,還帶公式合法性檢測呢,等我找找放哪了

好吧,找不到了,大致印象就是要做一個二維數組來判斷運算子優先權,然後計算用堆疊來實現