javascript - 前端面试的一道算法题
本文介绍了javascript - 前端面试的一道算法题的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
今天,下午有一个面试,二面的时候有道算法题,我对算法一窍不通,求大神解惑
题目是 实现计算加减乘除括号运算的函数 输入字符串 类似 (1+2)/4+5+(3+5)*3 类似的合法运算
能不能稍微讲解下大体思路是什么?面试大哥当时语重心长的说了声这是算法题,我想不应该是eval()这种实现吧?
解决方案
用调度场算法把中缀表达式改后缀表达式(逆波兰表达式)
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));
}
这篇关于javascript - 前端面试的一道算法题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文