前端面试的一道算法题

Question

今天，下午有一个面试，二面的时候有道算法题，我对算法一窍不通，求大神解惑

题目是 实现计算加减乘除括号运算的函数 输入字符串 类似 (1+2)/4+5+(3+5)*3 类似的合法运算
能不能稍微讲解下大体思路是什么？面试大哥当时语重心长的说了声这是算法题，我想不应该是eval()这种实现吧？

Answer 1

用调度场算法把中缀表达式改后缀表达式(逆波兰表达式)var A = '((112 + 2) * (32 + (43 + 45 - 46) * 12))';function is_op(val) {&nbsp; &nbsp; var op_string = '+-*/()';&nbsp; &nbsp; return op_string.indexOf(val) > -1;}function init_expression(expression) {&nbsp; &nbsp; var expression = expression.replace(/\s/g, ''),&nbsp; &nbsp; &nbsp; &nbsp; input_stack = [];&nbsp; &nbsp; input_stack.push(expression[0]);&nbsp; &nbsp; for (var i = 1; l = expression.length, i<l; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if (is_op(expression[i]) || is_op(input_stack.slice(-1))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; input_stack.push(expression[i]);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; input_stack.push(input_stack.pop()+expression[i]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return input_stack;}function op_level (op) {&nbsp; &nbsp; if (op == '+' || op == '-') {&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; if (op == '*' || op == '/') {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; if (op == '(') {&nbsp; &nbsp; &nbsp; &nbsp; return 3;&nbsp; &nbsp; }&nbsp; &nbsp; if (op == ')') {&nbsp; &nbsp; &nbsp; &nbsp; return 4;&nbsp; &nbsp; }}function RPN (input_stack) {&nbsp; &nbsp; var out_stack = [], op_stack = [], match = false, tmp_op;&nbsp; &nbsp; while (input_stack.length > 0 ) {&nbsp; &nbsp; &nbsp; &nbsp; var sign = input_stack.shift();&nbsp; &nbsp; &nbsp; &nbsp; if (!is_op(sign)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out_stack.push(sign);&nbsp; &nbsp; &nbsp; &nbsp; } else if (op_level(sign) == 4) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; match = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (op_stack.length > 0 ) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp_op = op_stack.pop();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ( tmp_op == '(') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; match = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out_stack.push(tmp_op);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (match == false) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 'lack left';&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while ( op_stack.length > 0 && op_stack.slice(-1) != '(' && op_level(sign) <= op_level(op_stack.slice(-1))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out_stack.push(op_stack.pop());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; op_stack.push(sign);&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; while (op_stack.length > 0 ){&nbsp; &nbsp; &nbsp; &nbsp; var tmp_op = op_stack.pop();&nbsp; &nbsp; &nbsp; &nbsp; if (tmp_op != '(') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out_stack.push(tmp_op);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 'lack right';&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return out_stack;}function cal(expression) {&nbsp; &nbsp; var i, j,&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; RPN_exp = [],&nbsp; &nbsp; &nbsp; &nbsp; ans;&nbsp; &nbsp; while (expression.length > 0) {&nbsp; &nbsp; &nbsp; &nbsp; var sign = expression.shift();&nbsp; &nbsp; &nbsp; &nbsp; if (!is_op(sign)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; RPN_exp.push(sign);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = parseFloat(RPN_exp.pop());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i = parseFloat(RPN_exp.pop());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; RPN_exp.push(cal_two(i, j, sign));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return RPN_exp[0];}function cal_two(i, j, sign) {&nbsp; &nbsp; switch (sign) {&nbsp; &nbsp; &nbsp; &nbsp; case '+':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i + j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; case '-':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i - j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; case '*':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i * j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; case '/':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i / j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; default:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }}var expression = RPN(init_expression(A))if (expression == 'lack left' || expression == 'lack right') {&nbsp; &nbsp; console.log(expression);} else {&nbsp; &nbsp; console.log(cal(expression));}