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

Answer 1

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) === 0

  Solution: 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:

• (recursive step) if it the symbol is an operator: calls the operator functions which uses readNextSymbol to fetch its arguments.
• (base case) if the symbol is a variable or constant: casts and returns the symbol.

---

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

Answer 2

I personally echo the sentiment in Ente's answer after reviewing the code provided in the question:

I would suggest abandoning this approach entirely.

After careful consideration of feedback in the comments below, I've boiled down my object-oriented approach to a conventional class style, and a more functional closure style.

The two styles share:

• a common interface,

  interface Expression {
    isConstant(void): boolean;
    toString(void): string;
    simplify(void): Expression;
  }
  

• two types Binary and Nullary, which implement the interface Expression and represent expressions of arity two or zero respectively,

• a Map of operators to binary functions,

  const operators = new Map([
    ['+', (a, b) => a + b],
    ['-', (a, b) => a - b],
    ['*', (a, b) => a * b],
    ['/', (a, b) => a / b]
  ]);
  

• and a static method.

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

The class style uses runtime polymorphism and defines the classes Binary and 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; }
}

The closure style defines two functions Binary() and Nullary(), each of which returns an object that implements the Expression interface:

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

^{Note that the new operator used in parse() is not necessary for calling the static functions defined in the closure style above.}

Finally, both of these read input and write output with the same boilerplate to call parse() and 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()}`);
});

_{Thanks Bergi for your feedback, which inspired me to write a closure-based approach.}

Answer 3

The steps to solve this problem are straightforward:

• start from the end of the line
• if you spot pattern: operator, number, number
  • replace these three items with the result of evaluation of the items

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

And if someone fancy longer but well-described functional code with reducers and higher-order functions, immutability* and referential transparency* which is great for unit testing, here it is:

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

^{* there's a small optimization that speeds the code up to 3 times but also makes part of the code impure. I'll leave the task of refactoring it for a curious reader ;)}