为运算表达式设计优先级-蒲公英云

为运算表达式设计优先级

た入场券 2022-12-24 04:53 299阅读 0赞

leetcode 241题 [medium]
中：为运算表达式设计优先级
英：Different Ways to Add Parentheses

题解

核心：递归分治 + 记事本优化

实现

/** * @param {string} input * @return {number[]} */
var diffWaysToCompute = function(input) { 
    /** * 递归分治法 + 记事本优化 */
    // 预处理 -- 无
    // 记事本
    let record = { };    // 键：表达式字符串, 值其可能的运算组合结果列表
    // 递归函数
    function recurse(_exp){ 
        // 预处理
        if(!Number.isNaN(Number(_exp))) return [Number(_exp)];  // 不是表达式，直接返回
        if(record[_exp]) return record[_exp];   // 读记事本
        // let result = new Set(); // 当前所有可能的运算结果，Set去重，后边转数组
        let result = [];              // 题目未去重
        let opMatch = [..._exp.matchAll(/[\+|\-|\*]/g)];
        for(let i=0, len=opMatch.length; i<len; i++){ 
            let currOp = opMatch[i][0];
            let currOpIndex = opMatch[i].index;
            let left = recurse(_exp.slice(0, currOpIndex));
            let right = recurse(_exp.slice(currOpIndex+1));
            for(let li=0; li<left.length; li++){ 
                for(let ri=0; ri<right.length; ri++){ 
                    result.push(eval(left[li] + ' ' + currOp + ' ' + right[ri]));
                }
            }
        }
        // 写记事本
        // result = [...result]; // 转数组
        record[_exp] = result;
        return result;
    }
    return recurse(input);
};