前缀表示法的简化

Question

前缀表示法的简化

5

我正在解决 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);
});

- Leff

我不会将其描述为“简化”，而是将其描述为“常量子表达式的求值”。 - user207421

4个回答

2

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

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

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

这两种风格共享以下内容：

a common interface,

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

two types Binary and Nullary, which implement the interface Expression and represent expressions of arity two or zero respectively,

a Map of operators to binary functions,

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

and a static method.

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

请注意，在上面的闭包风格中定义的静态函数中调用 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提供的反馈，这启发我编写基于闭包的方法。}

- Patrick Roberts

我建议您编写一个单独的simplified方法来返回一个新的Expression或数字/字符串，而不是将简化逻辑混合到toString方法中。 - Bergi

另外，您可能希望考虑使用“Expression”实例本身来表示文字（也许是“operator =””，“fn = parseInt”，“operands = [token]”）？然后，您可以使“parse”和“simplified”始终返回一个表达式，并将“isConstant”作为实例方法而不是静态方法。 - Bergi

@Bergi 我最初也尝试过这样做，但感觉过于工程化了，所以我决定对于这样的挑战，这个抽象层次已经足够了。 - Patrick Roberts

1

整个面向对象编程的方法对我来说有点过度设计（尽管我喜欢它的清晰度），但如果要采用它，我仍然会正确地实施它 :-) - Bergi

1

@PatrickRoberts 不完全是我想的（我为了简单起见只保留了一个类...），但你为走额外的一英里而获得了点赞 :-) 小问题：UnaryExpression 应该改为 NullaryExpression。 - Bergi

显示剩余3条评论

1

这种方法很可能无法通过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]

给定以下简化过程：

引用：简化过程就是尽可能地用值替换不包含变量的子表达式。

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

- customcommander

1

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

从行末开始
如果你发现模式：运算符、数字、数字
- 用这三个项的计算结果替换它们

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

如果有人喜欢更长但描述得很好的带有reducers和高阶函数、不可变性*和引用透明性*的功能代码，这对单元测试非常有用，那么这里就是它：

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倍，但也会使部分代码变得不纯。我会留下重构任务供好奇的读者完成 ;)}

- marzelin

3

除非参加代码高尔夫挑战，否则我会避免使用标记模板文字语法来调用普通函数。 - Bergi

@Bergi 当然，我不会在生产中使用它们，但由于它们看起来很棒，我喜欢将它们用于演示目的 :) - marzelin

1

它们可能看起来很棒（我不同意），但我认为它们是错误的：它们依赖于将数组参数转换为字符串的方法，这在大多数其他函数中可能会失败。在代码演示中使用这种风格将导致其他开发人员采用它，最终导致不良实践进入生产环境。 - Bergi

1

@Bergi 好的，为了促进良好的实践，我会修改它，并额外添加一个小优化;) - marzelin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ente · Accepted Answer

更新：尽管离完美还有很远的路要走，但代码在^[2]中的改进版本已经通过了Kattis上的所有测试。请参见下面的问题。

您原始代码存在以下几个问题^[1]：

对于输入+ / 1 2 1，您的代码输出：1，而不是正确的1.5。

原因是您在堆栈值上使用parseInt会将浮点数转换为整数，从而忽略该数字的小数部分。

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

原因是只有在处理变量或运算符时，代码才会将stack附加到result中

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

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