Упрощение префиксной записи

Я работаю над проблемой 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

Я написал этот фрагмент кода, и если я запустил его с такими входными данными, я получу точно такой же результат, как указано выше. Тем не менее, я получаю неправильный ответ от Каттис.

Что я здесь делаю не так? Это расстраивает, поскольку вы не получаете подсказок для отладки.

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);
});
Источник

4 ответа

Решение

обновление: хотя он далек от совершенства, улучшенная версия кода под [2] проходит все тесты на Kattis. См. Мои опасения ниже.

Есть несколько проблем с исходным кодом [1]:

  • Для ввода + / 1 2 1 ваш код дает: 1 вместо того 1.5.

    Причина в том, что вы используете parseInt на значениях стека, в результате чего числа с плавающей запятой преобразуются в целое число, игнорируя дробную часть указанного числа.

    Примеры:

    • parseInt(1/2) === 0
    • parseInt(2/3) === 0

    Решение: заменить все вхожденияparseInt с Number

  • Для ввода 1 ваш код дает: вместо того 1

    Причина в том, что stack только добавляется к result если код обрабатывает переменную или оператор

    Решение: делатьresult.unshift(...stack) после for-петля.

Найдите улучшенную версию кода в [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}`);
});
Источник

Я лично разделяю мнение Энте после просмотра кода, приведенного в вопросе:

Я бы предложил полностью отказаться от этого подхода.

После тщательного рассмотрения отзывов в комментариях ниже я свел свой объектно-ориентированный подход к обычному 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 оператор, используемый в 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 за ваш отзыв, который вдохновил меня на разработку подхода, основанного на закрытии.

Источник

Скорее всего, это не пройдет тестовый набор 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(' '));

Полный рабочий пример

⚠️Это использует Array.prototype.flat который не поддерживается в Edge.

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

Источник

Шаги для решения этой проблемы просты:

  • начать с конца строки
  • если вы заметили шаблон: оператор, номер, номер
    • замените эти три пункта на результат оценки пунктов
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 раз, но также делает часть кода нечистой. Оставлю задачу рефакторинга любознательному читателю;)

Источник
Другие вопросы по тегам