24点计算

24points.js

let input = process.argv[2].split(',').map((v)=>+v);
// let input = [6,6,6,6];
console.log('输入 %s', input.join(','));

let arr = input.concat(['o','o','o']);

let len = arr.length;

let isNumber = (item) => typeof item === 'number';

function log(p1, p2, p3){
    // console.log.apply(console, arguments);
}

function fillArr(arr, pickNumber, unique = true){
    if(typeof pickNumber === 'undefined') pickNumber = arr.length;
    let ret = [];
    if(pickNumber === 0){
        return ret;
    }
    log('------enter');
    for(let i=0;i<arr.length;i++){
        let thisNum = arr[i];
        let rest = arr.slice();
        // 元素是否不能重复出现
        if(unique){
            rest.splice(i, 1);
        }
        // console.log(rest.length, pickNumber);
        log('thisNum %d, rest:', thisNum, rest);
        if(pickNumber > 1){
            log('has rest');
            let restArr = fillArr(rest, pickNumber-1, unique);
            log('rest arr:', restArr);
            for(let j=0;j<restArr.length;j++){
                let arr = restArr[j].slice();
                arr.unshift(thisNum);
                ret.push(arr);
            }
        }else{
            log('no rest');
            ret.push([thisNum]);
        }
    }
    log('ret', ret);
    log('------exit');

    let retStr = ret.map((item) => item.join(','));
    log(retStr);
    return ret.filter((item, index) => {
        let itemStr = item.join(',');
        return index === retStr.lastIndexOf(itemStr);
    });
}

let ret = fillArr(arr);
console.log('数字+运算符占位组合后缀表达式数量 %d', ret.length);

ret = ret.filter((item) => {
    let opCount = -1;
    for(let i=0;i<item.length;i++){
        if(isNumber(item[i])){
            opCount++;
        }else{
            if(opCount <= 0){
                return false;
            }
            opCount--;
        }
    }
    return true;
});

console.log('数字+运算符占位组合筛选合法后缀表达式数量 %d', ret.length);

class TreeNode{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
    isEqual(tree){
        if(this.value !== tree.value) return;
        let valueEqual = function(v1, v2){
            if(!(v1 instanceof TreeNode) && !(v2 instanceof TreeNode)){
                // 两个都是值，直接比较
                return v1 === v2;
            }else if(v1 instanceof TreeNode && v2 instanceof TreeNode){
                // 两个都是树，递归比较
                return v1.isEqual(v2);
            }else{
                // 一个值，一个树，不等
                return false;
            }
        }
        let equal = valueEqual(this.left, tree.left) && valueEqual(this.right, tree.right);
        let reverseEqual = valueEqual(this.left, tree.right) && valueEqual(this.right, tree.left);
        if(this.value === '+' || this.value === '*'){
            return equal || reverseEqual;
        }else{
            return equal;
        }
    }
    toPostExp(){
        let left = '';
        if(this.left instanceof TreeNode){
            left = this.left.toPostExp();
        }else{
            left = this.left;
        }
        let right = '';
        if(this.right instanceof TreeNode){
            right = this.right.toPostExp();
        }else{
            right = this.right;
        }
        return left+','+right+','+this.value;
    }
    toMiddleExp(){
        let left = '';
        if(this.left instanceof TreeNode){
            left = '('+this.left.toMiddleExp()+')';
        }else{
            left = this.left;
        }
        let right = '';
        if(this.right instanceof TreeNode){
            right = '('+this.right.toMiddleExp()+')';
        }else{
            right = this.right;
        }
        return left+this.value+right;
    }
    clone(){
        let newTree = new TreeNode(this.value);
        if(this.left instanceof TreeNode){
            newTree.left = this.left.clone();
        }else{
            newTree.left = this.left;
        }
        if(this.right instanceof TreeNode){
            newTree.right = this.right.clone();
        }else{
            newTree.right = this.right;
        }
        return newTree;
    }
    fillOp(opList){
        let arr = opList;
        this.value = arr[0];
        arr = arr.slice(1);
        if(this.left instanceof TreeNode){
            arr = this.left.fillOp(arr);
        }
        if(this.right instanceof TreeNode){
            arr = this.right.fillOp(arr);
        }
        return arr;
    }
}

let treeList = ret.map((item) => {
    let stack = [];
    let tree;
    for(let i=0;i<item.length;i++){
        if(isNumber(item[i])){
            stack.push(item[i]);
        }else{
            tree = new TreeNode(item[i]);
            tree.left = stack.pop();
            tree.right = stack.pop();
            stack.push(tree);
        }
    }
    return stack.pop();
});

console.log('后缀表达式生成树结构数量 %d', treeList.length);

const opList = ['+', '-', '*', '/'];

const opArr = fillArr(opList, 3, false);
// console.log(opArr);
console.log('运算符组合数量 %d', opArr.length);

const opTreeList = [];
treeList.forEach((tree) => {
    opArr.forEach((op) => {
        const newTree = tree.clone();
        // console.log(tree, newTree);
        newTree.fillOp(op);
        opTreeList.push(newTree);
    });
});

console.log('树结构组合运算符数量 %d', opTreeList.length);

let pickedTreeList = [];
opTreeList.forEach((tree, index) => {
    if(!pickedTreeList.some((pickedTree) => {
        return pickedTree.isEqual(tree);
    })){
        pickedTreeList.push(tree);
    }
});

console.log('针对加法/乘法，树左右枝去重后数量 %d', pickedTreeList.length);


let result = false;
pickedTreeList.forEach((tree, index) => {
    let middleExp = tree.toMiddleExp();
    if(Math.abs(eval(middleExp) - 24) < 0.1){
        console.log(`第${index}次测试，找到解： ${middleExp}`);
        result = true;
    }
    // console.log(`testing ${middleExp} ${result}`);
});
if(!result){
    console.log(`共测试表达式${pickedTreeList.length}个，无解`);
}