4
\$\begingroup\$

This was the task (I don't know the exact wordings anymore):

You get a string with operation as input:

  1. if it is a number push it to stack
  2. if it is "DUP", then duplicate the one one top and push it to the stack
  3. if it is "POP" then remove the one on top
  4. if it is "+" add the two numbers on top of the stack and replace both with the result of the addition
  5. if it is "-" then minus the two numbers on top (the second minus the first) of the stack and replace both with the result of the subtraction
  6. if an error occurs, e.g. not enough numbers to add/subtract/pop, then return -1

Examples:

Input: "3 DUP 5 - -"
Output: -1

Input: "13 DUP 4 POP 5 DUP + DUP + -"
Output: 7

Input: "5 6 + -"
Output: -1

My approach is quite simple. I differentiate between numbers and operations. If it is a number I simply push it to the stack. Otherwise Ill check what kind of operation it is. If a valid operation is recognized, then the mapped function will be executed.

If an error occurs, e.g. no more numbers in the stack to be popped, invalid operation, etc. it will return -1.

My solution

function solution(S) {
    if (!S.length) {
        return -1;
    }
    const stack = new Array();
    const push = n => stack.push(Number(n));
    const pop = () => {
        if (!stack.length) {
            throw new Error('empty');            
        }
        return stack.pop();
    }
    const duplicate = () => {
        try {
            const dup = pop();
            push(dup);
            push(dup);            
        } catch(e) {
            throw new Error(e);    
        }
    };
    const add = () => {
        try {
            const sum1 = pop();
            const sum2 = pop();
            push(sum1 + sum2);            
        } catch(e) {
            throw new Error(e);    
        }
    };
    const minus = () => {
        try {
            const min1 = pop();
            const min2 = pop();
            push(min1 - min2);
        } catch(e) {
            throw new Error(e);    
        }
    };
    const ops = {
        "DUP": duplicate,
        "POP": pop,
        "+": add,
        "-": minus,
    };

    const input = S.split(' ');
    input.forEach(x => {
        if (!isNaN(x)) {
            push(x);
        } else {
            try {
                const sanitzedX = x.toUpperCase();
                if (!ops[sanitzedX]) {
                    return -1;
                }
                ops[sanitzedX]();
            } catch(e) {
                return -1;
            }
        }
    });
    try {
        return pop();
    } catch(e) {
        return -1;
    }
}

console.log(solution("3 DUP 5 - -"));
console.log(solution("13 DUP 4 POP 5 DUP + DUP + -"));
console.log(solution("5 6 + -"));
\$\endgroup\$
3
\$\begingroup\$

In JavaScript using exceptions to communicate standard logic information is rather bad. Exceptions are bulky and slow (some browsers can not optimise code containing try blocks). Your handling of errors will also mask real errors and thus let serious problems slip by while developing the code.

When you use exceptions always check the error in the catch to see if it is part of the functions proper execution, all other errors you should re throw.

Also use one try catch, there is no need to add try catches in every function.

Using exceptions

The rewrite cleans up your exception handling and adds a custom error StackError The one catch first checks the error and passes on all unrelated errors to a higher level.

function problem(S) {
    function StackError() {  }
    if (!S.length) { return -1 }
    const stack = [];
    const push = n => stack.push(Number(n));
    const pop = () => {
        if (stack.length) { return stack.pop() }
        throw new StackError();
    }
    const duplicate = () => {
        const dup = pop();
        push(dup);
        push(dup);            
    };
    const add = () => {
        const sum1 = pop();
        const sum2 = pop();
        push(sum1 + sum2);    
    };
    const minus = () => {
        const min1 = pop();
        const min2 = pop();
        push(min1 - min2);
    };
    const ops = {
        "DUP": duplicate,
        "POP": pop,
        "+": add,
        "-": minus,
    };

    const input = S.split(' ');
    try {   
        input.forEach(x => {
            if (!isNaN(x)) {
                push(x);
            } else {
                const op = ops[x.toUpperCase()];
                if (op) { op() } else { throw new StackError() }
            }
        });
        return pop();
    } catch(error) {
        if (!(error instanceof StackError)) { throw error }
        return -1;
    }
}

Without the error handling

The next rewrite handles the error state via a semaphore that when true is used to exit the function. This also shows why using for of loops makes the code less complex. (You can only exit early from a iteration function via an exception (or other hacks)

function problem(S) {
    if (!S.length) { return -1 }
    const stack = [];
    const push = n => stack.push(Number(n));
    var error = false;
    const pop = () => {
        if (stack.length) { return stack.pop() }
        return (error = true, -1);
    }
    const ops = {
        POP: pop,
        DUP() {
            const dup = pop();
            push(dup);
            push(dup);            
        },
        "+"() { push(pop() + pop()) },
        "-"() { push(pop() - pop()) }
    };
    for (const item of S.split(" ")) {
        if (!isNaN(item)) {
            push(item);
        } else {
            const op = ops[item];
            if (op) { op() }
            if (error) { return - 1 }
        }
    }
    return pop();
}

I removed some repeated code defining functions and then adding them to ops was just repeated definitions.

Performance

Pushing and popping from a stack is fast but will still incur memory allocation and release (GC) overheads. If the stack grows and shrinks a lot then this overhead becomes significant.

To avoid most of the allocation / de allocation overhead only grow the array and keep a pointer to the top of the stack.

The stack will never use more memory than it already does (well in fact using the pointer method uses less memory as de/allocation can result in duplicated arrays in RAM waiting for GC and the pointer method reduces the number of GC tasks)

function problem(instructionStr) {
  var err = false, len = 0, item;
  if (instructionStr.trim() === "") { return -1 }
  const defaultOp = () => isNaN(item) ? err = true : stack[len++] = Number(item);
  const stack = [], ops = {
    DUP() { len ? stack[len] = stack[len++ - 1] : err = true },
    POP() { len ? len-- : err = true },
    "+"() { --len ? stack[len - 1] = stack[len] + stack[len - 1] : err = true },
    "-"() { --len ? stack[len - 1] = stack[len] - stack[len - 1] : err = true }
  };
  for (item of instructionStr.split(" ")) {
    ops[item] ? ops[item]() : defaultOp();
    if (err) { return -1 }
  }
  return len ? stack[len - 1] : -1;
}

Re Optimization

I totally disagree with Joseph comment under his answer

"Pre-mature optimization is bad. I'd optimize for readability and reducing cognitive overhead first before anything else"

Optimization does not mean that the code is any less readable. Micro optimizations sum up and should be habit, not the exception. Readability is what people are accustomed to, and I think this is where such comments as Joseph's stem.

\$\endgroup\$
  • \$\begingroup\$ Why did you use var? \$\endgroup\$ – thadeuszlay Sep 27 at 13:11
  • \$\begingroup\$ @thadeuszlay to match the scope of the variable (function wide). I only use let for block scoped variables and then only under very specific use cases such as naming conflicts. . \$\endgroup\$ – Blindman67 Sep 27 at 13:21
  • 2
    \$\begingroup\$ Doesn't this add additional cognitive load if you add more concepts than neccessary? If you only had let and const than you only need to reason about these 2. Also what if I want to move the variable from function wide to a more narrow scope? Then I need to change it from var to let. Can you please explain to me the advantage of your approach? \$\endgroup\$ – thadeuszlay Sep 27 at 18:54
  • \$\begingroup\$ The problem I have with var is that it's subjunctive. It allows for many possible declarations, depending on which branch the code took earlier in the function. It's much easier to abuse this concept than to use it. \$\endgroup\$ – dfhwze Sep 28 at 20:33
  • \$\begingroup\$ @dfhwze i must disagree. A function should not be longer than a page (or two at the most) and its cyclomatic complexity should be kept as low as possible if you find that your use of a variable is "subjunctive" the cause is not the declaration type but rather the cause is the design of the function. let and const can have the same scope as var function args are vars. Vars should be hoisted. let by your reasoning encourages long complex function design. let is "subjunctive" in a way var can never be. Example for(let i=0;i<9;i++){ let r=d[i]; for(let i=0;i<9; i++){ rw[i]++ }} \$\endgroup\$ – Blindman67 Sep 29 at 0:37
3
\$\begingroup\$
const stack = new Array()

Use the literal notation ([]) instead. Here's an answer on Stack Overflow that elaborates why you should do that instead of new Array().

const duplicate = () => {
    try {
        const dup = pop();
        push(dup);
        push(dup);            
    } catch(e) {
        throw new Error(e);    
    }
};

The rule of thumb when it comes to using exceptions is to never use them where you can use an if. That is, don't use exceptions as a flow control mechanism. You should only use it if you want to bail out and do no further.

Also, e is already an instance of Error. You only need to do throw e, not throw new Error(e).

Now if you look closely, all the operations are distinct to each other. They also only operate on the stack only. You can easily implement them as pure functions, taking in the current stack, and returning a new representation of the stack.

For example, duplicate can be implemented as a function that takes an array, and returns a new array, with the last item repeated once more:

const duplicate = stack =>
  stack.length < 1 ? -1 
  : [...stack, stack[stack.length - 1]]

add can be implemented as a function that takes an array, and return an new array which replaces the last two items with their sum:

const add = stack =>
  stack.length < 2 ? -1 
  : [...stack.slice(0, -2), stack[stack.length - 1] + stack[stack.length - 2]]

Doing it this way makes it easier to implement each operation without having them becoming dependent on some common state object, or each other.

Here's how I would implement it:

// Implement each operation as distinct, pure functions.
const push = (stack, v) => [...stack, v]

const pop = stack => 
  stack.length < 1 ? -1
  : stack.slice(0, -1)

const duplicate = stack =>
  stack.length < 1 ? -1 
  : [...stack, stack[stack.length - 1]]

const add = stack =>
  stack.length < 2 ? -1 
  : [...stack.slice(0, -2), stack[stack.length - 1] + stack[stack.length - 2]]

const subtract = stack =>
  stack.length < 2 ? -1
  : [...stack.slice(0, -2), stack[stack.length - 1] - stack[stack.length - 2]]

// Map operation tokens to their implementation.
// Should we add more operations, we simply add the implementation and reference
// its token in this map
const operations = {
  'DUP': duplicate,
  'POP': pop,
  '+': add,
  '-': subtract
}

const solution = s => {

  // For each token, parse and process.
  // You can implement this piece using iteration functions, loops, or even recursion.
  // I'm just more accustomed to reduce because it can carry a value across iterations
  // which, in this case, holds the stack for me.
  const result = s.split(' ').reduce((stack, token) => {
  
    // If any operation returned -1, we return -1 all the way.
    return stack === -1 ? -1
      // If token is a number, push it to the stack.
      : !isNaN(parseFloat(token)) && isFinite(token) ? push(stack, Number(token))
      // If token is an operation, apply operation.
      : operations[token.toUpperCase()] ? operations[token.toUpperCase()](stack)
      // Unknown token.
      : -1

  // Our stack as initial reduce value, an empty array.
  }, [])

  // If the result is -1, then so be it. Otherwise, return the top of the stack.
  return result === -1 ? -1 : result[result.length - 1]
}

console.log(solution("3 DUP 5 - -"));
console.log(solution("13 DUP 4 POP 5 DUP + DUP + -"));
console.log(solution("5 6 + -"));

\$\endgroup\$
  • \$\begingroup\$ Isn't it ineffecient to use reduce? \$\endgroup\$ – thadeuszlay Sep 26 at 4:44
  • \$\begingroup\$ @thadeuszlay Sure, returning new arrays every time and array.reduce() may not be the most efficient way to do this. But this example is so small, any cons brought about by these approaches is practically negligible. Pre-mature optimization is bad. I'd optimize for readability and reducing cognitive overhead first before anything else. \$\endgroup\$ – Joseph Sep 26 at 12:30
  • \$\begingroup\$ How would you solve it if you have a huge set of input data, i.e. how would your solution look like, if the task would ask you to find not the most readable but most efficient algorithm? \$\endgroup\$ – thadeuszlay Sep 26 at 17:23

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.