Simplification of prefix notation

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

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.

Tags:

Javascript

Kattis

Prefix Notation

Recent Posts