241.为运算表达式设计优先级.md

241.为运算表达式设计优先级

/*
 * @lc app=leetcode.cn id=241 lang=typescript
 *
 * [241] 为运算表达式设计优先级
 */

// @lc code=start
function diffWaysToCompute(expression: string): number[] {}
// @lc code=end

解法 1: dfs

function diffWaysToCompute(expression: string): number[] {
  const strs: string[] = ['']
  const ops = {
    '+': (a: number, b: number) => a + b,
    '-': (a: number, b: number) => a - b,
    '*': (a: number, b: number) => a * b,
  }
  for (let ch of expression) {
    if (ops[ch]) strs.push(ch, '')
    else strs[strs.length - 1] += ch
  }
  const n = strs.length
  const cache: number[][][] = Array.from({ length: n }, () => new Array(n))
  const dfs = (st: number, en: number): number[] => {
    if (st === en) return [Number(strs[st])]
    if (cache[st][en]) return cache[st][en]
    let res: number[] = []
    for (let i = st; i <= en; i++) {
      const ch = strs[i]
      if (ops[ch]) {
        const a = dfs(st, i - 1),
          b = dfs(i + 1, en)
        for (let num of a) {
          for (let num1 of b) {
            res.push(ops[ch](num, num1))
          }
        }
      }
    }
    cache[st][en] = res
    return res
  }
  const res = dfs(0, n - 1)
  return res
}

Case

test.each([
  { input: { expression: '2-1-1' }, output: [0, 2] },
  { input: { expression: '2*3-4*5' }, output: [-34, -14, -10, -10, 10] },
])('input: expression = $input.expression', ({ input: { expression }, output }) => {
  expect(diffWaysToCompute(expression)).toIncludeSameMembers(output)
})