javascript - 简化前缀表示法(Simplification of prefix notation)

Question

I am working on a Kattis problem , where I am supposed to take the input in prefix notation, simplify it and return it in prefix notation as well.

(我正在研究Kattis 问题 ，在这里我应该以前缀表示法接受输入，将其简化并以前缀表示法返回。)

These are the examples of inputs and outputs:

(这些是输入和输出的示例：)

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

I have written this piece of code, and if I run it with this kind of input data, I get exactly the same output as stated above.

(我已经编写了这段代码，并且如果使用这种输入数据运行它，我将获得与上述完全相同的输出。)

Yet, I get wrong answer from Kattis.

(但是，我从Kattis那里得到了错误的答案。)

What is it that I am doing wrong here?

(我在这里做错了什么？)

It is frustrating since you get no debugging hints.

(由于没有任何调试提示，这令人沮丧。)

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

  ask by Leff translate from so

Answer 1

update: even though it's far away from prefect, the improved version of the code under ^[2] passes all tests on Kattis.

(更新：即使与完美无缘， ^[2]下代码的改进版本也通过了Kattis上的所有测试。)

See my concerns below.

(请参阅下面的问题。)

There are several issues with your original code ^[1] :

(您的原始代码^[1]有几个问题：)

• For the input + / 1 2 1 your code yields: 1 instead of 1.5 .

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

  The reason is your usage of parseInt on stack values which has the effect that floats are converted to an integer by ignoring the fractional part of said number.

  (原因是您对堆栈值使用了parseInt ，结果是通过忽略浮点数的小数部分，将浮点数转换为整数。)

  Examples:

  (例子：)

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

  Solution : replace all occurrences of parseInt with Number

  (解决方案 ：将所有出现的parseInt替换为Number)

• For the input 1 your code yields:

  (对于输入1您的代码将产生：)

  instead of 1

  (代替1)

  The reson for this is that the stack is only appended to result if the code is processing a variable or an operator

  (这样做的原因是，仅当代码正在处理变量或运算符时，才将stack追加到result)

  Solution : do result.unsift(...stack) after the for -loop.

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

Find the improved version of the code under ^[2] .

(在^[2]下找到代码的改进版本。)

This version passes all Kattis tests.

(此版本通过了所有Kattis测试。)

BUT : I can not guarantee that there are no other bugs.

(但是 ：我不能保证没有其他错误。)

Solving the puzzle the way you started it, feels so unnatural and unnecessarily complicated.

(以开始的方式解决难题，感觉如此不自然且不必要地复杂。)

For this reason I would suggest abandoning this approach entirely.

(因此，我建议完全放弃这种方法。)

The problem with the chosen solution is that it tries to simplify the expression while parsing it from right to left.

(所选解决方案的问题在于，它试图在简化表达式的同时从右到左进行解析。)

The whole point behind the prefix notation is that you can simplify expressions easily while parsing from left to right by always reading and processing one symbol at the time.

(前缀符号背后的全部要点是，您可以始终始终读取和处理一个符号，从而在从左向右解析的同时轻松简化表达式。)

You will find a much simpler solution to the problem if you do that.

(如果这样做，您将找到解决该问题的简单得多的解决方案。)

The key idea here is that you need a function readNextSymbol which reads a symbol and either:

(这里的关键思想是您需要一个readNextSymbol函数，该函数读取一个符号，并且可以：)

• (recursive step) if it the symbol is an operator: calls the operator functions which uses readNextSymbol to fetch its arguments.

  (（递归步骤），如果该符号是运算符：调用使用readNextSymbol提取其参数的运算符函数。)

• (base case) if the symbol is a variable or constant: casts and returns the symbol.

  (（基本情况）如果符号是变量或常量：强制转换并返回符号。)

---

^{[1] original code}(^{[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] working code}(^[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}`);
});