Hard coding problems and how to approach them in JavaScript
In the final journey of this coding problem saga, we explore the intensity of difficult coding problems, and honestly, the most realistic type of problems one will face in their daily work.
If you read through easy coding problems and medium coding problems, then you will remember reading that you sometimes have to plan for a problem to approach it correctly. In common times, this is known as architecting, design thinking, workshopping, and many other various terms.
A key principle of planning in software engineering is a large upswing of time savings, reliability, and testability.
Knowing the best way to approach the user story can save days on implementing a critical feature and that is often the difference between average software engineers and the world's best software engineers. As always, practice and patience can get you from point A to Z, and this problem will showcase exactly how.
Architecting around the problem
Similarly to the easy and medium guides, we have to put thinking through the paces here to elevate our attention to what the problem is asking us to accomplish. Through this example, I will showcase possible stages of this calculation and showcase new ways of approaching these solutions.
For example, let us start with the following LeetCode interview sample question and examples of the output:
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1"
Output: 2
Example 2:
Input: s = " 2-1 + 2 "
Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
// https://leetcode.com/problems/basic-calculator/
As described in the problem, we need to perform arithmetical calculations of the provided string, without using a built-in method, like eval, to return the total value of the equation. If you have used a scientific calculator, you know that this is a familiar concept, and maybe even remember the order of operations, PEMDAS (Parenthesis Exponents Multiplication Division Addition Subtraction).
It appears from the examples, that there will only be Parenthesis, Addition, and Subtraction, but we can be sure that the test cases will be rough on any non-big-o favorable code. A great starting place as always, is to write down the questions being asked, and the tasks at hand, and then decide how to approach them.
//// s is a string that contains an equation
//// s can contain, numbers, "+", "-", "(", and ")" strings
// 1. the numbers begin as a parameterized string
// 2. the first and following numbers need to be stored
// 3. the numbers need to be iterated over and solved
// 4. the numbers in the equation can be added
// 5. the numbers in the equation can be subtracted
// 6. the numbers in the equation could be negative
// 7. the numbers within parethesis need to be calculated inside the parethesis
// 8. the numbers calculated inside the parethesis need to be calculated as part of the equation
// 9. the result needs to be returned as the calculation of the parameter string
First coding approach
As you begin this problem you may see it in one way or another, if you are familiar with this type of problem, you may get to the answer more easily. Although the first time I looked at this type of problem, I knew what I needed to do, I continued to work through a lens that was a bit more robust.
It is worth exploring this first programming approach because it identifies what this problem may seem like and the lessons you can gather from having more information. The steps that I took through this initial process, took up hours of work, but eventually revealed that the complexity of this solution made its viability unimpactful.
Sometimes starting to code a problem and taking an approach is the only method to explore more challenges that are not immediately visible from the beginning.
In this approach, the theory was to parse the parenthesis, perform the equation within the parenthesis, and return that value to the index where the parenthesis started. This aligns with the solutions for easy, and medium problems, but you will see, that no matter how hard you try to make this solution work, there always seems to be some complexity to account for.
const math = (s) => {
const obj = {};
// Create array from s
obj["arr"] = Array.from(s);
// Remove empty strings from array
obj["clean"] = [];
// Consider multiple digits
obj["equation"] = [];
// Track equation result
obj["result"] = "";
// Remove empty strings
obj.arr.forEach((str) => {
if (str !== " " && str !== " " && str !== "" && str !== '"') {
obj["clean"].push(str);
}
});
// Join multiple digits + others
obj.clean.forEach((str, i) => {
if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5]) &&
parseInt(obj.clean[i + 6]) &&
parseInt(obj.clean[i + 7]) &&
parseInt(obj.clean[i + 8]) &&
parseInt(obj.clean[i + 9]) &&
parseInt(obj.clean[i + 10])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
temp["str"] += obj.clean[i + 6];
temp["str"] += obj.clean[i + 7];
temp["str"] += obj.clean[i + 8];
temp["str"] += obj.clean[i + 9];
temp["str"] += obj.clean[i + 10];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 10);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5]) &&
parseInt(obj.clean[i + 6]) &&
parseInt(obj.clean[i + 7]) &&
parseInt(obj.clean[i + 8]) &&
parseInt(obj.clean[i + 9])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
temp["str"] += obj.clean[i + 6];
temp["str"] += obj.clean[i + 7];
temp["str"] += obj.clean[i + 8];
temp["str"] += obj.clean[i + 9];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 9);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5]) &&
parseInt(obj.clean[i + 6]) &&
parseInt(obj.clean[i + 7]) &&
parseInt(obj.clean[i + 8])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
temp["str"] += obj.clean[i + 6];
temp["str"] += obj.clean[i + 7];
temp["str"] += obj.clean[i + 8];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 8);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5]) &&
parseInt(obj.clean[i + 6]) &&
parseInt(obj.clean[i + 7])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
temp["str"] += obj.clean[i + 6];
temp["str"] += obj.clean[i + 7];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 7);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5]) &&
parseInt(obj.clean[i + 6])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
temp["str"] += obj.clean[i + 6];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 6);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4]) &&
parseInt(obj.clean[i + 5])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
temp["str"] += obj.clean[i + 5];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 5);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3]) &&
parseInt(obj.clean[i + 4])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
temp["str"] += obj.clean[i + 4];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 4);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2]) &&
parseInt(obj.clean[i + 3])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
temp["str"] += obj.clean[i + 3];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 3);
} else if (
parseInt(str) &&
parseInt(obj.clean[i + 1]) &&
parseInt(obj.clean[i + 2])
) {
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
temp["str"] += obj.clean[i + 2];
obj["equation"].push(temp["str"]);
obj.clean.splice(i, 2);
} else if (
(parseInt(str) && parseInt(obj.clean[i + 1])) ||
(parseInt(str) && obj.clean[i + 1] === "0")
) {
// Two Digit Number
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
obj["equation"].push(temp["str"]);
obj.clean.splice(i - 1, 1);
} else if (
(str === "-" && obj.clean[i - 1] === "-" && parseInt(obj.clean[i + 1])) ||
(str === "-" && obj.clean[i - 1] === "+" && parseInt(obj.clean[i + 1]))
) {
// Negative Number
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
obj["equation"].push(temp["str"]);
obj.clean.splice(i - 1, 1);
} else if (
str === "-" &&
obj.clean[i - 1] === undefined &&
parseInt(obj.clean[i + 1])
) {
// Leading Negative Number
const temp = {};
temp["str"] = "";
temp["str"] += str;
temp["str"] += obj.clean[i + 1];
obj["equation"].push(temp["str"]);
obj.clean.splice(i + 1, 1);
} else if (str !== " " && str !== " " && str !== "" && str !== '"') {
obj["equation"].push(str);
}
});
// Perform math
obj.equation.forEach((str, i) => {
if (i === 0 && parseInt(str)) {
obj["result"] = parseInt(str);
} else if (str === "+" && parseInt(obj.equation[i + 1])) {
obj["result"] = obj.result + parseInt(obj.equation[i + 1]);
} else if (str === "-" && parseInt(obj.equation[i + 1])) {
obj["result"] = obj.result - parseInt(obj.equation[i + 1]);
}
});
return obj.result.toString();
};
const parentheses = (s) => {
const obj = {};
// Create array from s
obj["arr"] = Array.from(s);
// Remove shallow parentheses
obj.arr.forEach((str, i) => {
if (str === "(" && parseInt(obj.arr[i + 1]) && obj.arr[i + 2] === ")") {
obj["arr"].splice(i, 1);
obj["arr"].splice(i + 1, 1);
} else if (
str === "(" &&
parseInt(obj.arr[i + 1]) &&
parseInt(obj.arr[i + 2]) &&
obj.arr[i + 3] === ")"
) {
obj["arr"].splice(i, 1);
obj["arr"].splice(i + 2, 1);
} else if (
str === "(" &&
parseInt(obj.arr[i + 1]) &&
parseInt(obj.arr[i + 2]) &&
parseInt(obj.arr[i + 3]) &&
obj.arr[i + 4] === ")"
) {
obj["arr"].splice(i, 1);
obj["arr"].splice(i + 3, 1);
} else if (
str === "(" &&
parseInt(obj.arr[i + 1]) &&
parseInt(obj.arr[i + 2]) &&
parseInt(obj.arr[i + 3]) &&
parseInt(obj.arr[i + 4]) &&
obj.arr[i + 5] === ")"
) {
obj["arr"].splice(i, 1);
obj["arr"].splice(i + 4, 1);
} else if (
str === "(" &&
parseInt(obj.arr[i + 1]) &&
parseInt(obj.arr[i + 2]) &&
parseInt(obj.arr[i + 3]) &&
parseInt(obj.arr[i + 4]) &&
parseInt(obj.arr[i + 5]) &&
obj.arr[i + 6] === ")"
) {
obj["arr"].splice(i, 1);
obj["arr"].splice(i + 5, 1);
}
});
// Check for shallow parentheses with single digit numbers || Check for shallow parentheses with only equation left
if (
obj["arr"].length > 1 &&
obj["arr"].includes("(") &&
obj["arr"].includes(")")
) {
// Find last opening parentheses
obj["start"] = obj.arr.lastIndexOf("(");
// Find first closing parentheses
obj["end"] = 0;
// Track equation between parentheses
obj["s"] = "";
// Track equation result
obj["result"] = "";
// Remaining equation
obj["remaining"] = [];
// Final equation
obj["final"] = "";
// Find closing parentheses
obj.arr.forEach((str, i) => {
if (i > obj["start"] && obj["end"] === 0 && str === ")") {
obj["end"] = i;
}
});
// Create string from items between parentheses
obj.arr.forEach((str, i) => {
if (i > obj["start"] && i < obj["end"]) {
obj["s"] += str;
}
});
// Calculate items between parentheses
obj["result"] = math(obj.s);
// Replace items between parentheses with result
obj.arr.forEach((str, i) => {
if (i < obj["start"] || i > obj["end"]) {
obj["remaining"].push(str);
} else if (i === obj["start"]) {
obj["remaining"].push(obj.result);
}
});
// Return items to string
obj.remaining.forEach((str) => {
if (!(obj.start > 0) || !(obj.end > 0)) {
if (str !== "(" && str !== ")") {
obj["final"] += str;
}
} else {
obj["final"] += str;
}
});
} else {
obj["final"] = obj.arr;
}
// Check for double negative
if (obj.final.includes("--")) {
obj["final"] = obj.final.replace("--", "-");
}
// Check for plus negative
if (obj.final.includes("+-")) {
obj["final"] = obj.final.replace("+-", "-");
}
return obj.final;
};
const calculate = function (s) {
const obj = {};
// Track full equation
obj["s"] = s;
// Track negative resolution
obj["negative"] = false;
// Check for negative resolution
if (obj["s"][0] === "-" && !parseInt(obj["s"][1]) && obj["s"][1] !== "(") {
obj["negative"] = true;
obj["arr"] = Array.from(obj.s);
obj["s"] = "";
// Remove negative start
obj.arr.forEach((str, i) => {
if (i > 0) {
obj["s"] += str;
}
});
}
while (obj["s"].includes("(") && obj["s"].includes(")")) {
obj["s"] = parentheses(obj.s);
}
// If equation does not contain parentheses
if (!obj["s"].includes("(") && !obj["s"].includes(")")) {
obj["s"] = math(obj.s);
}
if (obj["negative"]) {
return obj.s - obj.s * 2;
} else {
return obj.s;
}
};
These three functions above consider almost every type of mathematical rule and parameter complexity, they will get you most of the way through the test cases. As you reach the end of the cases, you will see that the complexity in the parenthesis by sheer volume tends to augment the solution's ability to perform the math.
You can log the intermittent math equation, and what you end up seeing, although this parses the parenthesis well, the order of operations left between the +/- considerations miscalculates the equation.
Second coding approach
As you begin to make progress, then lose progress, and make progress with the test cases it is a good sign that at some point you may need to pivot the solution to adjust. You can see, working through this problem, that as a problem evolves, and this is often the case in the day-to-day, code needs to be refactored or adjusted to account for the changing principles.
Working through this after-hours that led to days of submissions, it may be a good time to start thinking outside of the box. We often see loops and object polymorphism, so we are focused on writing programs that handle exception visibility. As a GitHub Copilot subscriber, I figured I would try to sus out some of the mechanics behind this solution to see if it could be changed to a passing outcome.
As you can see, GitHub Copilot reads the code from the file that is open and responds to the inputs that are provided to it. In this instance, the prompt provided was ‘Fix the code in place without eval()’ which in the example above, GitHub Copilot refactored the math function of the code.
Working with this newly created math function begins to consider the actual requirements for this problem. As you can see, these lines of code parse the values and perform the math based on a stack algorithm, which works more like a parser.
// Enhanced by GitHub Copilot
const math = (s) => {
const obj = {};
// Create array from s
obj["arr"] = Array.from(s);
// Remove empty strings from array
obj["clean"] = obj["arr"].filter((str) => str.trim() !== "");
// Consider multiple digits
obj["equation"] = [];
// Track equation result
obj["result"] = 0;
// Join multiple digits + others
let currentNumber = "";
obj.clean.forEach((str, i) => {
if (
!isNaN(parseInt(str)) ||
(str === "-" &&
currentNumber === "" &&
(i === 0 || "+-*/".includes(obj.clean[i - 1])))
) {
// It's part of a number
currentNumber += str;
} else {
if (currentNumber !== "") {
// Push the number we've been building up
obj.equation.push(parseFloat(currentNumber));
currentNumber = ""; // Reset for the next number
}
// It's an operator or parentheses
obj.equation.push(str);
}
});
// Don't forget to add the last number if there is one
if (currentNumber !== "") {
obj.equation.push(parseFloat(currentNumber));
}
// Implement a simple parser for + and - operations
let stack = [];
obj.equation.forEach((token) => {
if (typeof token === "number") {
stack.push(token);
} else if (token === "+") {
stack.push("+");
} else if (token === "-") {
stack.push("-");
} else if (token === "(") {
stack.push("(");
} else if (token === ")") {
let acc = 0;
let items = [];
while (stack[stack.length - 1] !== "(") {
items.push(stack.pop());
}
stack.pop(); // remove '('
items.reverse();
let currentOp = "+";
items.forEach((item) => {
if (item === "+" || item === "-") {
currentOp = item;
} else {
acc = currentOp === "+" ? acc + item : acc - item;
}
});
stack.push(acc);
}
});
// Final calculation
let acc = 0;
let currentOp = "+";
stack.forEach((item) => {
if (item === "+" || item === "-") {
currentOp = item;
} else {
acc = currentOp === "+" ? acc + item : acc - item;
}
});
obj.result = acc;
return obj.result;
};
This new function does progress further into the test cases than any previous adjustments, and logic reveals that the code may need to be more dynamic. The break here occurs when the equation parameter of s
becomes a larger series of characters or bytes, which makes the equation evaluate slower.
You can recognize two items here that are key to solving this problem if you went down this path, it is simply too robust and built up to be performant. The other, is simply that maybe it is a good point to reevaluate how you are approaching the problem and find different ideas.
Returning to the todos
After hours, days, and a lot of time spent thinking about this problem, I decided to look for an outside source. In our day to day, we often only reference documentation or rely on memory to lead us to a solution. It is rare to find a problem that requires this much attention and often, that is a good point, for the sake of everyone, to start searching the internet for ideas.
You can tell that the principle here is correct, we need to parse the characters that are not numbers and evaluate them while handling their considerations mathematically. The insight we gained from working through this and from referencing GitHub Copilot, is that we should try to handle this equation with stacks.
- Our first consideration in this problem is encountering numbers and identifying how to handle them. We know that these numbers will need to be stored, and we need to streamline how this is stored for reference.
We are starting with a string as the equation, therefore to be able to access the for each method, we need to convert the string to an array. Although a string in JavaScript can be referenced as an array based on an index, we need to convert the string to an array to work with it more dynamically. The Array.from static method copies the string into an array and makes this possible.
const obj = {};
obj["arr"] = Array.from(s);
// 2. the first and following numbers need to be stored
// 3. the numbers need to be iterated over and solved
// 4. the numbers in the equation can be added
// 5. the numbers in the equation can be subtracted
// 6. the numbers in the equation could be negative
// 7. the numbers within parethesis need to be calculated inside the parethesis
// 8. the numbers calculated inside the parethesis need to be calculated as part of the equation
// 9. the result needs to be returned as the calculation of the parameter string
2. When we talk about storing numbers, this could be an array, a string, or an object, the biggest challenge is workability, and in that focus, an object is the primary way to handle updates without hassle and immutability.
We can store the numbers in an object, along with the result of addition or subtraction, the negative or positive context of an equation, and any equations that need to be stored until the parenthesis ends. These are the primary factors provided by the explanation, which we attempted to handle before by parsing, but can be streamlined with a stack data structure.
const obj = {};
obj["arr"] = Array.from(s);
obj["number"] = 0;
obj["result"] = 0;
obj["outcome"] = 1;
obj["operation"] = [];
// 3. the numbers need to be iterated over and solved
// 4. the numbers in the equation can be added
// 5. the numbers in the equation can be subtracted
// 6. the numbers in the equation could be negative
// 7. the numbers within parethesis need to be calculated inside the parethesis
// 8. the numbers calculated inside the parethesis need to be calculated as part of the equation
// 9. the result needs to be returned as the calculation of the parameter string
3. As the operation begins, we need to loop over the indices of the array to handle each index with its respective conditions, so we need to begin creating a loop with conditions to evaluate the array or in this case, stack.
The for each method here combined with if…else will allow for an index-by-index approach that passes each value of the stack independently through the function.
When working with numbers the parseInt method converts a string that is a number, into a number/integer, which can be used to evaluate in an if condition because it will evaluate to false if the string is not a number.
An additional aspect of this is adding the isNan method so that in the case of the number zero, the parseInt will parse the value, but zero in the if condition will be evaluated as the binary zero and not pass this condition as it should.
As each number passes through the condition, we can store it in the object number key, to assign multi-character numbers, as we are parsing through them individually, we need to scale the original number to accept the secondary position and so on. For the number three to accept zero as a secondary digit to make thirty, we must make three thirty and add the zero. There are various ways of performing these mathematical considerations in JavaScript, in this fashion where we are merging digits, we have to create a contextual radix.
const obj = {};
obj["arr"] = Array.from(s);
obj["number"] = 0;
obj["result"] = 0;
obj["outcome"] = 1;
obj["operation"] = [];
obj.arr.forEach((str, i) => {
if (!isNaN(parseInt(str))) {
obj.number = obj.number * 10 + parseInt(str);
}
});
// 4. the numbers in the equation can be added
// 5. the numbers in the equation can be subtracted
// 6. the numbers in the equation could be negative
// 7. the numbers within parethesis need to be calculated inside the parethesis
// 8. the numbers calculated inside the parethesis need to be calculated as part of the equation
// 9. the result needs to be returned as the calculation of the parameter string
4/5/6. When parsing the equation, there may be +/- considerations that appear as strings at the index, we need to accommodate those accordingly and mind their consideration within the equation respectively.
In the positive and negative outcomes, we use the outcome value to hold the state of the equation. In an addition equation we are adding the number to the existing number, in subtraction we are adding the inverse of the number to the existing number. Negative numbers are considered here, through concatenating the numbers and processing them through subtraction. We store the value of +/- in the result with the += (addition assignment) operator, and after the equation, we set the number to zero.
const obj = {};
obj["arr"] = Array.from(s);
obj["number"] = 0;
obj["result"] = 0;
obj["outcome"] = 1;
obj["operation"] = [];
obj.arr.forEach((str, i) => {
if (!isNaN(parseInt(str))) {
obj["number"] = obj.number * 10 + parseInt(str);
} else if (str === "+") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = 1;
obj["number"] = 0;
} else if (str === "-") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = -1;
obj["number"] = 0;
}
});
// 7. the numbers within parethesis need to be calculated inside the parethesis
// 8. the numbers calculated inside the parethesis need to be calculated as part of the equation
// 9. the result needs to be returned as the calculation of the parameter string
7/8. As we know from the explanation the trickiest part of this problem is that there are parenthesis, we need to consider the order of operations within the stack, storing the equations between the opening and closing parenthesis as their own stack.
From the beginning of the parentheses, we begin to store the proceeding values within the operation, along with their positive/negative outcome, proceeding through the indices until reaching the closing parentheses. Any intermediary equations are solved, stored, and pushed to populate the operation array.
Once the parentheses are ending, we first reset the result using the outcome and number through the += (addition assignment) operator. We then pop the stack which retrieves the last index, and use the *= (multiplication assignment) operator to create our contextual radix. We then again pop the last index and add that to the result to evaluate the remaining numbers in the temporary stack using the += (addition assignment) operator.
const obj = {};
obj["arr"] = Array.from(s);
obj["number"] = 0;
obj["result"] = 0;
obj["outcome"] = 1;
obj["operation"] = [];
obj.arr.forEach((str, i) => {
if (!isNaN(parseInt(str))) {
obj["number"] = obj.number * 10 + parseInt(str);
} else if (str === "+") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = 1;
obj["number"] = 0;
} else if (str === "-") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = -1;
obj["number"] = 0;
} else if (str === "(") {
obj["operation"].push(obj.result);
obj["operation"].push(obj.outcome);
obj["result"] = 0;
obj["outcome"] = 1;
} else if (str === ")") {
obj["result"] += obj.outcome * obj.number;
obj["result"] *= obj["operation"].pop();
obj["result"] += obj["operation"].pop();
obj["number"] = 0;
}
});
// 9. the result needs to be returned as the calculation of the parameter string
9. Once we have worked through the problem, in this sense, looped through all of the indices, we need to return the stored result as a number that represents the final result.
In this final step, we perform a full cleanup by returning the result, plus the remaining number, multiplied by the outcome of positive/negative. In this scenario, we escape a lot of the finite stages of these problems, from leading negatives to parenthesis order of operations, and even training numbers.
const obj = {};
obj["arr"] = Array.from(s);
obj["number"] = 0;
obj["result"] = 0;
obj["outcome"] = 1;
obj["operation"] = [];
obj.arr.forEach((str, i) => {
if (!isNaN(parseInt(str))) {
obj["number"] = obj.number * 10 + parseInt(str);
} else if (str === "+") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = 1;
obj["number"] = 0;
} else if (str === "-") {
obj["result"] += obj.number * obj.outcome;
obj["outcome"] = -1;
obj["number"] = 0;
} else if (str === "(") {
obj["operation"].push(obj.result);
obj["operation"].push(obj.outcome);
obj["result"] = 0;
obj["outcome"] = 1;
} else if (str === ")") {
obj["result"] += obj.outcome * obj.number;
obj["result"] *= obj["operation"].pop();
obj["result"] += obj["operation"].pop();
obj["number"] = 0;
}
});
return obj.result + obj.number * obj.outcome;
Considering the problem
Working through this problem you will probably begin to further understand the importance of considering the best way to approach the problem before starting. The initial solutions for the problem took days of work, only to be met with test cases that eventually timed out due to the amount of considerations hand-coded as functionality.
As you look this over you will conclude that there are few unique ways to solve this problem, other than ignoring the actual mathematical challenge and building in methods for outsourcing the calculations. This becomes an exemplary question for understanding what happens under the hood in these languages. When you have built-in functions that handle these sorts of equations natively, you often become accustomed to building up large data-focused functions that in this scenario are a non-performant solution.
You can find my solution to the ‘Basic Calculator’ problem on LeetCode.
As a static method, an example of the function may look something like the one below, where this can be called within other code to provide calculations:
Sometimes thinking out of the box in programming leads to the best solution, here the answer is determined by understanding the type of data structure we are working on.
If we look at this as a data transformation problem we build handlers and exceptions, if we understand that this is a stack to be evaluated, we can work more efficiently in creating a matching algorithm.
Computer scientists working on problems like this often look to algorithms for compression, mathematics, machine learning, and many other paradigms to optimize their solutions.
We can understand, having worked through this problem, that code is not one size fits all and we need to keep our minds fresh to solve with new coding practices. Evaluating and becoming familiar with these problems is a continuous learning process that enables us to further our knowledge of programming. You can understand this problem more by reading through how to process a data structure like stacks with online learning tools.