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);
});
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]:
For the input + / 1 2 1 your code yields: 1 instead of 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.
Examples:
parseInt(1/2) === 0 parseInt(2/3) === 0Solution: replace all occurrences of parseInt with Number
For the input 1 your code yields: instead of 1
The reason for this is that the stack is only appended to result if the code is processing a variable or an operator
Solution: do result.unshift(...stack) after the for-loop.
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:
readNextSymbol to fetch its arguments.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);
});
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}`);
});