javascript - 前缀符号的简化

Question

我正在研究一个 Kattis问题，我应该以前缀表示法接受输入，将其简化并以前缀表示法返回。这些是输入和输出的示例：

Sample Input 1                    Sample Output 1
+ 3 4                             Case 1: 7
- x x                             Case 2: - x x
* - 6 + x -6 - - 9 6 * 0 c        Case 3: * - 6 + x -6 - 3 * 0 c

我已经编写了这段代码，如果我使用这种输入数据运行它，我会得到与上述完全相同的输出。然而，我从 Kattis 那里得到了错误的答案。

我在这里做错了什么？这是令人沮丧的，因为您没有得到调试提示。

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const operators = ['+', '-', '*', '/'];
const operatorsFunctions = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b,
};

let lineNumber = 0;

rl.on('line', (line) => {
    const mathExpression = line.split(' ');
    lineNumber += 1;
    let result = [];
    let stack = [];

    for (let i = mathExpression.length -1; i >= 0; i--) {
        if (!isNaN(mathExpression[i])) {
            stack.unshift(mathExpression[i]);
        } else if (operators.includes(mathExpression[i])){
            if (!stack.length) {
                result.unshift(mathExpression[i]);
            }
            if (stack.length === 1) {
                result.unshift(stack[0]);
                result.unshift(mathExpression[i]);
                stack = [];
            }
            if (stack.length > 1) {
                const sum = operatorsFunctions[mathExpression[i]](Number(stack[0]), Number(stack[1]))
                stack.splice(0, 2, sum);
                if (i === 0) {
                    result.unshift(...stack);
                }
            }
        } else {
            if (stack.length) {
                result.unshift(...stack);
                stack = [];
            }
            result.unshift(mathExpression[i]);
        }
    }
    const text = `Case ${lineNumber}: ${result.join(' ')}`;
    console.log(text);
});

score 4 · Accepted Answer

更新：尽管它远非完美，但^[2]下代码的改进版本通过了 Kattis 上的所有测试。请参阅下面我的担忧。

^{您的原始代码[1]}存在几个问题：

对于输入，+ / 1 2 1您的代码产生：1而不是1.5.

原因是您parseInt对堆栈值的使用具有通过忽略所述数字的小数部分将浮点数转换为整数的效果。

例子：
- parseInt(1/2) === 0
- parseInt(2/3) === 0
解决方案：替换所有出现的parseIntwithNumber
对于1您的代码产生的输入：而不是1

原因是只有在代码正在处理变量或运算符stack时才附加result

解决方案：result.unshift(...stack)在for-loop 之后执行。

^在[2]下找到代码的改进版本。该版本通过了所有 Kattis 测试。

但是：我不能保证没有其他错误。以你开始的方式解决难题，感觉如此不自然和不必要的复杂。出于这个原因，我建议完全放弃这种方法。所选择的解决方案的问题在于它试图在从右到左解析表达式时简化表达式。前缀符号背后的全部意义在于，您可以在从左到右解析的同时通过始终读取和处理一个符号轻松简化表达式。如果你这样做，你会找到一个更简单的问题解决方案。这里的关键思想是您需要一个readNextSymbol读取符号的函数，并且：

（递归步骤）如果符号是运算符：调用readNextSymbol用于获取其参数的运算符函数。
（基本情况）如果符号是变量或常量：强制转换并返回符号。

^{[1] 原代码}

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const operators = ['+', '-', '*', '/'];
const operatorsFunctions = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b,
};

let lineNumber = 0;

rl.on('line', (line) => {
    const mathExpression = line.split(' ');
    lineNumber += 1;
    let result = [];
    let stack = [];

    for (let i = mathExpression.length -1; i >= 0; i--) {
        if (!isNaN(mathExpression[i])) {
            stack.unshift(mathExpression[i]);
        } else if (operators.includes(mathExpression[i])){
            if (!stack.length) {
                result.unshift(mathExpression[i]);
            }
            if (stack.length === 1) {
                result.unshift(stack[0]);
                result.unshift(mathExpression[i]);
                stack = [];
            }
            if (stack.length > 1) {
                const sum = operatorsFunctions[mathExpression[i]](parseInt(stack[0]), parseInt(stack[1]))
                stack.splice(0, 2, sum);
                if (i === 0) {
                    result.unshift(...stack);
                }
            }
        } else {
            if (stack.length) {
                result.unshift(...stack);
                stack = [];
            }
            result.unshift(mathExpression[i]);
        }
    }
    const text = `Case ${lineNumber}: ${result.join(' ')}`;
    console.log(text);
});

^{[2] 工作代码}

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const operators = ['+', '-', '*', '/'];
const operatorsFunctions = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b,
};

function parse(line) {
    const mathExpression = line.split(' ');
    let result = [];
    let stack = [];

    for (let i = mathExpression.length -1; i >= 0; i--) {
        if (!isNaN(mathExpression[i])) {
            stack.unshift(mathExpression[i]);
        } else if (operators.includes(mathExpression[i])){
            if (!stack.length) {
                result.unshift(mathExpression[i]);
            }
            if (stack.length === 1) {
                result.unshift(stack[0]);
                result.unshift(mathExpression[i]);
                stack = [];
            }
            if (stack.length > 1) {
                const sum = operatorsFunctions[mathExpression[i]](
                  Number(stack[0]), 
                  Number(stack[1])
                )
                stack.splice(0, 2, sum);
            }
        } else {
            if (stack.length) {
                result.unshift(...stack);
                stack = [];
            }
            result.unshift(mathExpression[i]);
        }
    }
    result.unshift(...stack);
    return result.join(' ');
}


let lineNumber = 0;
rl.on('line', (line) => {
  lineNumber += 1;
  let answer = parse(line);
  console.log(`Case ${lineNumber}: ${answer}`);
});

score 2 · Accepted Answer

在查看了问题中提供的代码后，我个人在Ente 的回答中回应了这种观点：

我建议完全放弃这种方法。

在仔细考虑了下面评论中的反馈后，我将我的面向对象方法归结为传统class风格和更实用的闭包风格。

两种风格共享：

一个通用接口，

interface Expression {
  isConstant(void): boolean;
  toString(void): string;
  simplify(void): Expression;
}

两种类型Binary和Nullary，它们实现接口Expression并分别表示二元或零的表达式，

一个Map二元函数的运算符，

const operators = new Map([
  ['+', (a, b) => a + b],
  ['-', (a, b) => a - b],
  ['*', (a, b) => a * b],
  ['/', (a, b) => a / b]
]);

和一个静态方法。

function parse (tokens) {
  const token = tokens.shift();

  if (!operators.has(token)) {
    return new Nullary(token);
  }

  const a = parse(tokens);
  const b = parse(tokens);

  return new Binary(token, a, b);
}

类风格使用运行时多态性并定义类Binary和Nullary：

class Binary {
  constructor (op, a, b) {
    this.op = op;
    this.operands = [a, b];
    this.f = operators.get(op);
  }

  isConstant () {
    return this.operands.every(e => e.isConstant());
  }
  toString () {
    return `${this.op} ${this.operands.join(' ')}`;
  }
  simplify () {
    const args = this.operands.map(e => e.simplify());

    return args.every(e => e.isConstant())
    ? new Nullary(`${this.f(...args.map(Number))}`)
    : new Binary(this.op, ...args);
  }
}

class Nullary {
  constructor (value) {
    this.value = value;
  }

  isConstant () { return !isNaN(this.value); }
  toString () { return this.value; }
  simplify () { return this; }
}

闭包风格定义了两个函数Binary()和Nullary()，每个函数都返回一个实现Expression接口的对象：

function Binary (op, a, b) {
  const operands = [a, b];
  const f = operators.get(op);

  return {
    isConstant: () => operands.every(e => e.isConstant()),
    toString: () => `${op} ${operands.join(' ')}`,
    simplify: () => {
      const args = operands.map(e => e.simplify());

      return args.every(e => e.isConstant())
      ? Nullary(`${f(...args.map(Number))}`)
      : Binary(op, ...args)
    }
  };
}

function Nullary (value) {
  const self = {
    isConstant: () => !isNaN(value),
    toString: () => value,
    simplify: () => self
  };

  return self;
}

^{请注意，在调用上述闭包样式中定义的静态函数时，不需要new使用 in 运算符。parse()}

最后，这两个读取输入和写入输出都使用相同的样板来调用parse()和expression.simplify()：

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let lineNo = 0;

rl.on('line', line => {
  const tokens = line.split(/\s+/g);
  const expression = parse(tokens);

  console.log(`Case ${++lineNo}: ${expression.simplify()}`);
});

_{感谢Bergi的反馈，这启发了我编写基于闭包的方法。}

score 1 · Accepted Answer

这很可能不会通过 Kattis 测试套件，但我只是想分享另一种方法

我首先将表达式转换为数据结构：

tokenize('+ x + 10 20');
//=> ['+', 'x', ['+', '10', '20']]

为什么？它允许我们递归地解释“OA B”表达式：

const simplify_expr = ([o, a, b]) =>
  interpret(
    [ o
    , is_expr(a) ? simplify_expr(a) : evaluate(a)
    , is_expr(b) ? simplify_expr(b) : evaluate(b)
    ]);

simplify_expr(['+', 'x', ['+', '10', '20']]);
//=> ['+', 'x', 30]

给定以下简化过程：

简化过程只是尽可能用它们的值替换不包含变量的子表达式。

那么interpret函数可以写成如下：

const interpret = ([o, a, b]) =>
    typeof a !== 'number' || typeof b !== 'number' ? [o, a, b]
  : o === '*' ? a * b
  : o === '/' ? a / b
  : o === '+' ? a + b
              : a - b;

interpret(['+', 10, 20]);
//=> 30

如何将表达式转换为数据结构？

拆分字符串：

'+ x + 10 + 20 30'.split(' ')
//=> ['+', 'x', '+', '10', '+', '20', '30']

然后从右到左递归，直到将所有表达式按三个一组进行分组：

['+', 'x', '+', '10', '+', '20', '30']     // length > 3
['+', 'x', '+', '10', ['+', '20', '30']]   // length > 3
['+', 'x', ['+', '10', ['+', '20', '30']]] // length 3 stop!

可能的实现：

const group_expr = xs =>
  xs.length <= 3
    ? xs
    : is_expr(xs.slice(-3))
      ? group_expr(
          [ ...xs.slice(0, -3)
          , xs.slice(-3)
          ])
      : group_expr(
          [ ...xs.slice(0, -4)
          , xs.slice(-4, -1)
          , ...xs.slice(-1)
          ]);

const tokenize = str =>
  group_expr(str.split(' '));

完整的工作示例

⚠️EdgeArray.prototype.flat不支持此用途。

const evaluate = x =>
  Number(x) == x
    ? Number(x)
    : x;

const is_expr = x =>
  Array.isArray(x) &&
  ( x[0] === '*' ||
    x[0] === '/' ||
    x[0] === '+' ||
    x[0] === '-' );

const group_expr = xs =>
  xs.length <= 3
    ? xs
    : is_expr(xs.slice(-3))
      ? group_expr(
          [ ...xs.slice(0, -3)
          , xs.slice(-3)
          ])
      : group_expr(
          [ ...xs.slice(0, -4)
          , xs.slice(-4, -1)
          , ...xs.slice(-1)
          ]);

const tokenize = str =>
  group_expr(str.split(' '));

const interpret = ([o, a, b]) =>
    typeof a !== 'number' || typeof b !== 'number' ? [o, a, b]
  : o === '*' ? a * b
  : o === '/' ? a / b
  : o === '+' ? a + b
              : a - b;

const simplify_expr = ([o, a, b]) =>
  interpret(
    [ o
    , is_expr(a) ? simplify_expr(a) : evaluate(a)
    , is_expr(b) ? simplify_expr(b) : evaluate(b)
    ]);

const simplify = str => {
  const expr = simplify_expr(tokenize(str));
  return Array.isArray(expr)
    ? expr.flat(Infinity).join(' ')
    : String(expr);
};

console.log(simplify('+ 3 4'));
console.log(simplify('- x x'));
console.log(simplify('* - 6 + x -6 - - 9 6 * 0 c'));
console.log(simplify('+ x + 10 + 20 30'));

score 1 · Accepted Answer

解决这个问题的步骤很简单：

从行尾开始
如果您发现模式：运算符，数字，数字
- 将这三个项目替换为项目的评估结果

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const ops = ["+", "-", "/", "*"];
let lineNumber = 0;

rl.on('line', (line) => {
    lineNumber += 1;
    let exp = line.split(" ");
    for (let i = exp.length - 2; i >= 0 ; i--) {
        if (ops.includes(exp[i])) {
            if (![exp[i+1], exp[i+2]].map(Number).some(Number.isNaN)) {
                exp.splice(i, 3, eval([exp[i+1], exp[i], exp[i+2]].join(" ")));
            } else { // a letter detected - we can safely skip two items
               i -= 2;
            }
        }
    }

    console.log(`Case ${lineNumber}: ${exp.join(" ")}`);
});

如果有人喜欢更长但描述良好的函数式代码，其中包含 reducer 和高阶函数、不变性* 和引用透明性*，这对单元测试非常有用，这里是：

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let lineNumber = 0;
rl.on("line", line => {
  lineNumber += 1;
  let tokens = line.split(" ");
  let simplified = tokens.reduceRight(simplify(), []);

  console.log(`Case ${lineNumber}: ${simplified.join(" ")}`);
});

function simplify() {
  const operations = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "*": (a, b) => a * b,
    "/": (a, b) => a / b
  };
  const skip = { val: 2 };
  const doWork = createDoWork(skip, operations);
  return (simplified, token) => {
    if (skip.val) {
      skip.val--;
      return [token, ...simplified];
    }
    return doWork(simplified, token);
  };
}

function createDoWork(skip, operations) {
  const isOperator = createIsOperator(operations);
  const replaceWithEvaluation = createReplaceWithEvaluation(operations);
  return (simplified, token) => {
    if (isOperator(token)) {
      if (firstTwoAreNumbers(simplified)) {
        return replaceWithEvaluation(token, simplified);
      }
      skip.val = 2;
    }
    return [token, ...simplified];
  };
}

function createIsOperator(operations) {
  const operationTokens = Object.keys(operations);
  return token => operationTokens.includes(token);
}

function firstTwoAreNumbers(arr) {
  return !arr
    .slice(0, 2)
    .map(Number)
    .some(Number.isNaN);
}

function createReplaceWithEvaluation(operations) {
  return (operator, simplified) => {
    const [n1, n2, ...rest] = simplified;
    const evaluation = operations[operator](+n1, +n2);
    return [evaluation, ...rest];
  };
}

^{* 有一个小的优化，可以将代码速度提高 3 倍，但也会使部分代码不纯。我将把重构它的任务留给好奇的读者；）}

javascript - 前缀符号的简化

4 回答 4

[1] 原代码

[2] 工作代码

如何将表达式转换为数据结构？

完整的工作示例

Related

Reference

^{[1] 原代码}

^{[2] 工作代码}