1
\$\begingroup\$

I have to create a program which calculates the result of an arithmetic term written in Polish Notation.

var parseNotation = parseNotation || {};

/**
 * Computes the result of an given arithmetic term which is written in
 *  Reverse Polish Notation (https://en.wikipedia.org/wiki/Reverse_Polish_notation).
 * @param { String } termInReversePolish - The operators / operands of
 *  the term have to be separated by colons. See usage example!
 * @return { number } Result of the given term.
 * @throws { Error } Will throw an error in case of no or invalid parameter
 *  is given.
 * 
 * Usage example (will display 37 as result):
 *  console.log(parseNotation.computeFromReversePolish('5,6,2,+,*,12,4,/,-'));
 */

parseNotation.computeFromReversePolish = function(termInReversePolish) {
  var currentChar = '';
  var stack = [];
  var right = 0;

  if (typeof termInReversePolish !== 'string') {
    throw new Error(
      `No valid parameter given. String expected but ${typeof termInReversePolish} found.`);
  }
  
  if (termInReversePolish.search(/[^\d,+*\/-]/g) != -1) {
      throw new Error(
        'Given parameter contains illegal characters. Valid characters are: + - * / , 0-9');
  }

  termInReversePolish = termInReversePolish.split(',');

  termInReversePolish.forEach((currentChar, i) => {
    if (['+', '-', '*', '/'].indexOf(currentChar) === -1) {
      stack.push(currentChar);
    } else {
      right = stack.pop();

      stack.push(eval(stack.pop() + currentChar + right));
    }
  });
  
  return stack.pop();
}

// ---- Testing ------------------
console.log(parseNotation.computeFromReversePolish( '1,2,+,3,4,+,*' ));
console.log(parseNotation.computeFromReversePolish( '5,6,2,+,*,12,4,/,-' ));
console.log(parseNotation.computeFromReversePolish( '2,7,+3,/,14,3,-,4,*,+,2,/' ));

My first few test with the function have gone well. Nevertheless, I would like to read the opinion of other developer, especially regarding:

  • Is my documentation done in a proper way? Or does I have to improve it?

  • Is my parameter validation sufficient? Especially regarding the used regular expression.

  • Generally: Is everything done in a good way and fashion?

If someone sees an error or flaw then please let me know.

\$\endgroup\$
1
\$\begingroup\$

To start at the end:

Generally: Is everything done in a good way and fashion?

It looks quite good, kudos!

Structurally, there's one thing that's not quite right, though: You're declaring currentChar and right in the function's scope, you really don't need to. The currentChar you've declared never gets used; the argument in the forEach callback shadows it (and it's not necessarily a character - it could be "12312"). And right doesn't have to be in that scope either, it can just be local to the callback.

And you could technically use reduce instead of forEach with a closed-over stack, but that's not so bad.

I also have some more notes, but also I'm nit-picking quite a bit. I had to find something to write, y'know?

Your documentation seems fine. The exact flavor of documentation syntax is more or less up to you (JS doesn't have a strong convention), so the JavaDoc-like syntax is fine. Would also have accepted a regular comment without the @-keywords, so long as the important parts are covered.

You might consider some comments in the function body, though. There isn't much need for it here admittedly, but just to say that it's not just about commenting the API but also the code.

The regex validation seems fine too, but it doesn't catch malformed syntax, only illegal tokens. A string like ",,," wouldn't trigger anything, nor would a string like "3,+".

The latter ("3,+") returns NaN, which is sort of OK. You can evoke the rule of "Garbage in, garbage out" and blame the caller. At least they're getting a Number back (yes, NaN - not a number - is in fact a Number. Go figure.)

The former input, however, returns an empty string. Since no operations have been performed, the final stack.pop() will be an empty string. So here, you're not even getting a number. That seems less correct.

Ideally, you would complain if the function reaches the end with something other than 1 element in the stack, since that would imply that the RPN expression wasn't "balanced". In fact, your third example suffers from this; the stack ends at [2, 23.1666...], but you report the 23.166... as the answer despite the expression not being fully parsed.

It would also be nice to allow (and ignore) whitespace in the string, just to make input a little flexible. A more readable input string might be beneficial to users (I tested your code, and kept putting in spaces after commas out of habit).

There's another thing your code doesn't handle: Anything with decimals. Since you can't use . in the string, you're limited to integers. That's a bit harsh. You could also consider allowing other legal JS number formats like 0x3 hex, 0b1010 binary, or 3.14e3, but that's more just an exercise for you. eval should already handle them fine, but your regex will complain.

Last bit about validation: I'd throw a TypeError if the input isn't a string. More accurate than a generic Error certainly.

That's mostly smaller stuff, and easily fixed or left as-is. The only thing I'd do very differently would be to not use eval. If you instead define the operators as functions, you:

  1. get rid of eval, which is always nicer in my opinion
  2. you can implement operators that don't take 2 operands such as factorial
  3. you can easily implement more operators (right now, you'll have to change both the regex and the array in the loop)

And if you store your functions in an object, you get quicker lookup than with indexOf (not that that really matters that much).

For instance:

function rpn(expression) {
  // define our operators as functions
  const operators = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b,
    '^': Math.pow
  };

  // check input type
  if (typeof expression !== 'string') {
    throw new TypeError(`No valid parameter given. Expected string but got ${typeof expression}.`);
  }

  // evaluate the expression, ignoring whitespace
  var stack = expression.replace(/\s/g, '').split(',').reduce((stack, term) => {
    if (operators.hasOwnProperty(term)) {
      const op = operators[term];

      // check stack depth
      if (stack.length < op.length) {
        throw new Error("Stack underflow");
      }

      // grab n elements from the stack, where n is the number of arguments
      // that the operator function takes
      var operands = stack.splice(-op.length);

      // perform the operation and push the result
      stack.push(op.apply(null, operands));
    } else {
      var number = term * 1; // coerce the term to a number

      // check that the coercion produced something numeric
      if (Number.isNaN(number)) {
        throw new Error(`The term '${term}' is neither numeric or a recognized operator`);
      }

      stack.push(number);
    }

    return stack;
  }, []);

  if (stack.length !== 1) {
    throw new Error("Incomplete expression"); // find something better to say
  }

  return stack[0];
}
\$\endgroup\$
  • \$\begingroup\$ Awesome. Thanks a lot for all answers. Can accept only one answer but they are definitely all three helpful. \$\endgroup\$ – michael.zech Feb 6 '17 at 6:29
1
\$\begingroup\$

Is my parameter validation sufficient? Especially regarding the used regular expression.

No. Your regular expression only tests for the used character class, but does not evaluate the semantic structure at all.

While it is - to my knowledge - not possible to inject arbitrary executable code into the context, due to not having access to parenthesis ( or ), it's still easy enough to provoke an syntax error during evaluation.

You also don't validate your stack. Not ensuring that it is empty at the end of your function is just a matter of lacking input validation.

Not validating that it doesn't underflow during execution is slightly nastier, because this can result in Array.prototype.pop() returning undefined, which then when casting to string results in "undefined", which then again during the eval casts to the identifier undefined which can - other than the name suggests - be defined.

'2,7,+3,/,14,3,-,4,*,+,2,/'

This isn't even valid reverse polish notation, with the 3rd term which includes both an operator and an operand. And yet your implementation did happily process this, including the resulting side effects.

Is my documentation done in a proper way? Or does I have to improve it?

You should not refer to an example section just to explain the basic syntax. If you need to do that, chance is that your syntax is bloated.

In this case, it would have been a better choice to pass directly an Array to your function. That both removes the need for half of your code, and provides a simpler interface.

\$\endgroup\$
1
\$\begingroup\$

Documentation

You should not overestimate documentation. If your variables, functions and classes are named properly and you try not to distorte reality in your model you help to avoid looking into the documention. Documentation for me is not neccessarily a problem but for me it is an indicator of poor code quality. The truth lies in the executable parts of your source code nowhere else. And those should be as understandable as possible.

If you really want to produce beneficial documentation for a developer you should provide expressive tests that shows how to use your API and tell him/her about the restrictions.

General notes and Parameter validation

Maybe for the usecase you have to implement the provided solution may be sufficient.

If you introduce new elements like brackets or whitespaces you will have to violate the Open-Closed-Principle as you do not go the general way of parsing. Your approach does not consider language extensions to be easy. You can see where your parsing is neglected as you introduce unnecessary delimitters (,) to separate each element properly. If you want to be flexible for language extension and avoid such artifice you should consider the Interpreter-pattern and the State-Pattern. Additional you should have a look at automaton theory.

If you follow this path you do not need a parameter validation as you would be able to identify the exact position of the language violation during parsing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.