Heim > Fragen und Antworten > Hauptteil
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?
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));
}
漂亮男人2017-05-19 10:29:19
最通用的方法是语法分析,构建表达式树,然后求解。
你可以自己写,也可以用一个很专业很通用的库叫Antlr。
当然面试的时候应该是让你自己分析语法构建语法树了,真正做的时候还是Antlr更好一些。
巴扎黑2017-05-19 10:29:19
我不推荐采用eval这个被抛弃的方法。一.推荐使用正则表达式 二.使用数据结构中的栈的方法
推荐一本书:学习JavaScript数据结构与算法
最近刚好在研究栈,队列,二叉树这些东西
大家讲道理2017-05-19 10:29:19
用栈来实现,两年前我做数据结构实验的时候歇过一个,还带公式合法性检测呢,等我找找放哪了
好吧,找不到了,大致印象就是要做一个二维数组来判断运算符优先级,然后计算用栈来实现