javascriptprefix-notation

Simplification of prefix notation


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. 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.

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

Solution

  • update: even though it's far away from perfect, the improved version of the code under [2] passes all tests on Kattis. See my concerns below.

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

    Find the improved version of the code under [2]. This version passes all Kattis tests.

    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:


    [1] original code

    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

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