возвращающее уравнение со всеми возможными комбинациями скобок и результатом каждого

Question

В недавнем интервью меня попросили вернуть все возможные комбинации порядка операций на входной строке и результат. вы должны вернуть все пути/комбинации, в которых вы можете «принудительно» выполнять операции со скобками. Я получил результат (правая часть уравнения), но застрял на левой стороне. как я мог сделать левую и правую стороны вместе? Похоже, две проблемы в одном ...

//input: 
console.log(diffWaysToCompute("2 * 3 - 4 * 5")); 
//output: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10 

'use strict' 

function getNumbersAndOperators(str) { 
    var arr = str.split(" "); 
    var operators = []; 
    for (var i = 0; i < arr.length; i++) { 
    if (arr[i] === "-" || arr[i] === "*" || arr[i] === "+") { 
     operators.push(arr[i]); 
     arr.splice(i, 1); 
     // console.log(operators); 
    } 
    } 
    return [arr, operators]; 
} 
// console.log(getNumbersAndOperators("2 - 1 - 1")) 
var diffWaysToCompute = function (input) { 
    // var numbers = input.split(" "); 
    // console.log(numbers); 
    // // console.log(number); 
    var results = compute(input); 
    results.sort(function (a, b) { 
    return a - b; 
    }); 

    //put the numbers length into valid parenthesis: 
    var NumbersAndOperators = getNumbersAndOperators(input); 
    var numbers = NumbersAndOperators[0]; 
    console.log(numbers); 
    var operators = NumbersAndOperators[1]; 
    console.log(operators); 
    var parens = validParentheses(numbers.length); 
    // console.log(numbers); 
    console.log(operators); 

    // for (var i = 0; i < parens.length; i++) { 
    // for (var j = 0; j < parens[i].length; j++) { 
    //  var val = parens[i][j]; 
    //  console.log(val); 
    //  if (val === " ") { 
    //  var num = numbers.shift(); 
    //  parens.splice(val, 0, num); 
    //  //starting running into infinite loops and out of time. 
    //  j--; 
    //  } 
    // } 
    // i--; 
    // } 
    console.log(parens); 
    return results; 
}; 

function validParentheses(n) { 
    if (n === 1) { 
    return ['()']; 
    } 
    var prevParentheses = validParentheses(n - 1); 
    var list = {}; 
    prevParentheses.forEach(function (item) { 
    list['(' + item + ')'] = null; 
    list['()' + item] = null; 
    list[item + '()'] = null; 
    }); 
    console.log(Object.keys(list)) 
    return Object.keys(list); 
} 

function compute(str) { 
    var res = []; 
    var i; 
    var j; 
    var k; 
    var left; 
    var right; 
    var string = []; 
    var placed = true; 

    if (!/[+*-]/.test(str)) { // + - * 
    return [parseInt(str)]; 
    } 
    for (i = 0; i < str.length; i++) { 
    if (/\+|\-|\*/.test(str[i])) { // + - * 

     left = compute(str.substring(0, i)); 
     right = compute(str.substring(i + 1, str.length)); 
     for (j = 0; j < left.length; j++) { 
     for (k = 0; k < right.length; k++) { 

      if (str[i] === '+') { 
      res.push(parseInt(left[j] + right[k])); 
      } else if (str[i] === '-') { 
      // string.push("(" + str[i-2], str[i+2] + ")"); 

      res.push(parseInt(left[j] - right[k])); 
      } else if (str[i] === '*') { 

      res.push(parseInt(left[j] * right[k])); 
      } 
     } 
     } 
    } 
    } 


    // console.log(string); 
    return res; 
} 


console.log(diffWaysToCompute("2 - 1 - 1")); 
console.log(diffWaysToCompute("2 * 3 - 4 * 5")); 

Answer 1

Yikes. Это было сложно. Хорошая задача. Я уверен, что это может быть сокращено, но оно работает. Я использовал lodash и разбил различные функции, чтобы сделать его более гибким. Вот jsfiddle: https://jsfiddle.net/mckinleymedia/3e8g22Lk/8/

К сожалению, при добавлении parseInt в дополнение это не добавляется как строка.

/* 
//input: 
diffWaysToCompute("2 * 3 - 4 * 5"); 

//output: 
(2*(3-(4*5))) = -34 - 2,1,0 
((2*3)-(4*5)) = -14 - 0,2,1 & 2,0,1 
((2*(3-4))*5) = -10 - 1,0,2 
(2*((3-4)*5)) = -10 - 1,2,0 
(((2*3)-4)*5) = 10 - 0,1,2 
*/ 

'use strict' 
var diffWaysToCompute = function(str) { 
    var opsAvailable = ['+','-','/','*'], 
     numbers = [], 
     operators = [], 
     getNumbersAndOperators = function(str) { 
      var arr = str.split(" "); 
      for (var i in arr) { 
       if (opsAvailable.indexOf(arr[i]) > -1) { 
        operators.push(arr[i]); 
       } else { 
        numbers.push(arr[i]); 
       } 
      }; 
      return; 
     }, 
     permutator = function(range) { 
      var results = []; 
      function permute(arr, memo) { 
       var cur, 
        memo = memo || []; 
       for (var i in arr) { 
        cur = arr.splice(i, 1); 
        if (arr.length === 0) results.push(memo.concat(cur)); 
        permute(arr.slice(), memo.concat(cur)); 
        arr.splice(i, 0, cur[0]); 
       } 
       return results; 
      } 
      return permute(_.range(range)); 
     }, 
     equations = function(perms) { 
      var results = []; 
      _.each(perms, function(perm, k) { 
       results[k] = nest (perm); 
      }); 
      return results; 
     }, 
     nest = function(perm) { 
      var eqs = eqs || [], 
       ref = ref || _.range(perm.length).map(function() { return undefined }), 
       eq, 
       target = undefined; 
      for (var i in perm) { 
       var cur = perm[i], 
       next = perm[i] + 1, 
       n1 = numbers[ cur ], 
       n2 = numbers[ next ], 
       r1 = ref[ cur ], 
       r2 = ref[ next ]; 
       if (r1 !== undefined) n1 = eqs [ r1 ]; 
       if (r2 !== undefined) n2 = eqs [ r2 ]; 
       var rNew; 
       rNew = eqs.length; 
       for (var x in ref) { 
        if ((ref[ x ] !== undefined) && (ref[ x ] == r1 || ref[ x ] == r2)) ref[ x ] = eqs.length; 
       }; 
       ref[ cur ] = ref[ next ] = eqs.length; 
       eqs.push({ 
        ops: operators[ cur ], 
        nums: [ n1, n2 ] 
       }); 
      }; 

      return eqs[ eqs.length - 1 ]; 
     }, 
     calculations = function (eqs) { 
      var results = [] 
      _.each(eqs, function(equation) { 
       results.push(calculate(equation)); 
      }); 
      return results; 
     }, 
     calculate = function(eq) { 
      var result = { 
       text: "" 
      }; 
      // result.eq = eq; 
      result.text += "("; 
      result.total = eq.nums[ 0 ]; 
      if (_.isObject(result.total)) { 
       var result1 = calculate(result.total); 
       result.total = result1.total; 
       result.text += result1.text; 
      } else { 
       result.text += eq.nums[ 0 ]; 
      } 
      _.each(eq.ops, function (op, k) { 
       var num = eq.nums[ k + 1 ]; 
       result.text += " " + op + " "; 
       if (_.isObject(num)) { 
        var result2 = calculate(num); 
        num = result2.total; 
        result.text += result2.text; 
       } else { 
       result.text += num; 
       } 
       if (op === '+') result.total = parseInt(result.total) + parseInt(num); 
       if (op === '-') result.total = result.total - num; 
       if (op === '/') result.total = result.total/num; 
       if (op === '*') result.total = result.total * num; 
      }); 
      result.text += ")"; 
      return result; 
     }, 
     display = function(as) { 
      var target = document.getElementById('result'); 
      target.innerHTML += '<h3 class="problem">String given: ' + str + '</h3>'; 
      target.innerHTML += '<h4>Permutations</h4>'; 
      _.each(as, function(a) { 
       target.innerHTML += '<div class="permutation">'; 
       target.innerHTML += ' <span class="formula">' + a.text + '</span> = '; 
       target.innerHTML += ' <span class="total">' + a.total + '</span>'; 
       target.innerHTML += '</div>'; 
      }); 
     }, 
     perms, 
     eqs, 
     answers; 

     getNumbersAndOperators(str); 
     perms = permutator(operators.length); 
     eqs = equations(perms); 
     answers = calculations(eqs); 
     answers = _.uniq(answers, 'text'); 
     display(answers); 
    return answers; 
}; 
console.log(diffWaysToCompute("2 * 3 - 4 * 5")); 

Answer 2

я никогда не приходилось делать такие глупые вещи, так что позвольте мне попробовать свои зубы на него сейчас. (Протест как всегда: это очень упрощенная и без каких-либо проверок & остатки!)

Парсер самое простое здесь:

/* 
    Use of strings instead of ASCII codes for legibility. 

    I changed x - y to x + (-y) not only for convenience 
    but for algebraic correctness, too. 

    @param a array number nodes 
    @param o array operator nodes 

*/ 
function parse(s,a,o){ 
    var fnum = 0; 
    var uminus = false 
    for(var i=0;i<s.length;i++){ 
    switch(s[i]){ 
     case '-': uminus = true; 
       a.push(fnum); 
       o.push('+'); 
       fnum = 0; 
       break; 
     case '+': 
     case '*': 
     case '/': if(uminus){ 
        uminus = false; 
        fnum *= -1; 
       } 
       a.push(fnum); 
       o.push(s[i]); 
       fnum = 0; 
       break; 
     case '0': 
     case '1': 
     case '2': 
     case '3': 
     case '4': 
     case '5': 
     case '6': 
     case '7': 
     case '8': 
     case '9': fnum = fnum * 10 + parseInt(s[i]); 
       break; 
     default: break; 
    } 
    } 
    //assuming symmetry 
    a.push(fnum); 
} 

The (поколения мне потребовалось некоторое время, слишком много time-- Я обманул здесь ;-)

/* 
    Found in an old notebook (ported from C) 
    Algo. is O(n^2) and can be done faster but I 
    couldn't be a...ehm, had no time, sorry. 

    @idx int index into individual result 
    @n  int number of groups 
    @open int number of opening parentheses 
    @close int number of closing parentheses 
    @a  array individual result 
    @all array space for all results 
*/ 
function makeParens(idx,n,open,close,a,all){ 
    if(close == n){ 
    all.push(a.slice(0)); 
    return; 
    } else { 
    if(open > close){ 
     a[idx] = ')'; 
     makeParens(idx+1,n,open,close+1,a,all); 
    } 
    if(open < n){ 
     a[idx] = '('; 
     makeParens(idx+1,n,open+1,close,a,all); 
    } 
    } 
} 

А теперь? Yepp, что мне потребовалось некоторое время:

/* 
    The interesting part 
    Not very optimized but working 

    @s string the equation 
    @return array nicely formatted result 
*/ 
function parenthesing(s){ 
    var nums = []; 
    var ops = []; 
    var all = []; 
    var parens = []; 

    // parse input into numbers and operators 
    parse(input,nums,ops); 
    /* 
    Rules: 

    1) out-most parentheses must be open in direction to center 
     e.g.: (1+2+3), 1+(2+3), 1+(2+3)+4 
     but not: 1)+(2+3)+(4 
     so: first parenthesis on the left side must be open and 
      the last parenthesis on the right side must be close 

    2) parentheses in direct neighborhood to a number must be 
     open in direction to the number (multiplication is 
     not mutual) 
     e.g.: 1+(2+3)+4, but not: 1+2(+3+4) 

    3) parentheses in direct neighborhood to an operator must be 
     closed in direction to the operator (multiplication is 
     not mutual) 
     e.g.: 1+(2+3)+4, but not: 1+2(+3+)4 
    */ 
    // build combinations separately not in-line 
    // it's already a mess, no need to add more 
    makeParens(0,nums.length,0,0,[],parens); 
    // You may take a look at the raw material here 
    // console.log(parens.join("\n")); 
    for(var i= 0;i<parens.length;i++){ 
    var term = []; 
    // work on copies to reduce pointer juggling 
    var _ops = ops.slice(0); 
    var _nums = nums.slice(0); 
    for(var j=0;j<parens[i].length;j++){ 
     if(parens[i][j] === '('){ 
     term.push("("); 
     // rule 3 
     if(parens[i][j+1] === ')'){ 
      term.push(_nums.shift()); 
     } 
     // rules 1,2 
     else { 
      term.push(_nums.shift()); 
      term.push(_ops.shift()); 
     } 
     } 
     if(parens[i][j] === ')'){ 
     term.push(")"); 
     // rules 2,3 
     if(parens[i][j+1] !== ')') 
      term.push(_ops.shift()); 
     } 
    } 
    // some pretty printing 
    term = term.join(""); 
    // eval() because I didn't want to write a parser 
    // but if you need one... 
    all.push(term + " = " + eval(term)); 
    } 
    return all; 
} 

Я не уверен, если бы я получить работу с , что мерзости. Ах, если честно: я в этом сомневаюсь.

Но я надеюсь, что это хотя бы немного полезно.