前缀符号的简化

Question

我正在研究 Kattis problem，我应该在其中输入前缀符号，简化它并 return 它也用前缀符号。这些是输入和输出的示例：

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);
});

Answer 1

update: 虽然离完美还很远，但是^[2]下的改进版代码通过了Kattis上的所有测试.请参阅下面我的担忧。

你的原始代码有几个问题^[1]:

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

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

示例：
- parseInt(1/2) === 0
- parseInt(2/3) === 0
解决方案：将所有出现的parseInt替换为Number
对于输入 1 您的代码产生：</code> 而不是 <code>1

原因是 stack 仅在代码处理变量或运算符时附加到 result

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

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

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

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

^[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}`);
});

Answer 2

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

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

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(" ")}`);
});

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

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 倍，但也使部分代码不纯。我将把重构它的任务留给一个好奇的 reader ;)}

Answer 3

在查看问题中提供的代码后，我个人赞同中的观点：

I would suggest abandoning this approach entirely.

在仔细考虑下面评论中的反馈后，我将面向对象的方法归结为传统的 class style, and a more functional closure 风格。

两种风格分享：

普通interface,

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

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

一个 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);
}

class 样式使用运行时 polymorphism 并定义 classes 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()，每个函数returns一个实现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;
}

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

最后，这两个读取输入和写入输出都使用相同的样板来调用 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 for your ，它启发了我编写基于闭包的方法。}

Answer 4

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

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

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

为什么？它允许我们递归地解释 "O 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)
    ]);

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

给定以下简化程序：

The simplification procedure is just replacing subexpressions that contain no variables with their values wherever possible.

那么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(' '));

完整的工作示例

⚠️这使用了 Edge 不支持的 Array.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'));

前缀符号的简化

Simplification of prefix notation

javascript

prefix-notation

^[1]原码

^{[2] 工作码}

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

完整的工作示例