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

Answer 1

更新：尽管离完美还很远，^[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}`);
});