Problem
This was the task (I don’t know the exact wordings anymore):
You get a string with operation as input:
- if it is a number push it to stack
- if it is “DUP”, then duplicate the one one top and push it to the
stack- if it is “POP” then remove the one on top
- if it is “+” add the two numbers on top of the stack and replace
both with the result of the addition- 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- 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 + -"));
Solution
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.
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 + -"));