Build a Calculator

Let's build a very basic calculator by programming it! You've probably seen one that look similar to this:

But we won't be building a physical calculator (HardwareDaily will need to wait!)-- instead, we'll be writing a simple program that can serve as one. Can you write a function that will evaluate a simple expression string without using your language's eval method?

const expr = "2 + 2";
calculator(expr)
// 4

expr = "2 + 2"
calculator(expr)
# 4

It should also be able to handle positive and negative symbols +,-, parentheses (), and spaces.

let expr = "3 - 1 + 2";
calculator(expr)
// 4

expr = "(2+(4+2)-1)-(5+8)"
calculator(expr)
// -6

expr = "3 - 1 + 2"
calculator(expr)
# 4

expr = "(2+(4+2)-1)-(5+8)"
calculator(expr)
# -6

Assume for now that you don't need to handle multiplication or division cases.

Constraints

• Length of the given string <= 100000
• The numbers present in the string will be a single digit number
• Expected time complexity : O(n)
• Expected space complexity : O(n)

```js
function calculator(str) {
  // implement this method
	return str;
}
```

Setting the Stage: The Art of Mathematical Evaluation

Calculators, those nifty little devices that have saved us during countless math classes. But what if we could replicate that magic in software?

The idea is to build a "software calculator" that can evaluate mathematical expressions. Our goal is to evaluate expressions like 2 + 2 and (2+(4+2)-1)-(5+8) without using the built-in eval function in any language.

Why Skip the eval Function?

You might wonder, "If there's a built-in way to evaluate code strings, why not just use it?" Well, that's a great question! The eval function is quite handy, but it has its drawbacks:

• Security Risks: Using eval can expose your code to security vulnerabilities.
• Limited Customization: What if you want to extend the calculator functionality? With eval, you're stuck with what the language offers.
• Learning Opportunity: Building our own calculator is an excellent exercise for understanding parsing and evaluation algorithms.

How eval Works, Anyway?

Just to give you an idea, if we were to use eval, you could evaluate an expression like this:

console.log(eval("1+1"));

print(eval("1+1"))

// Java doesn't have a direct `eval` equivalent, but you can use libraries like ScriptEngine
import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
import javax.script.ScriptException;

public class Main {
    public static void main(String[] args) {
        ScriptEngineManager mgr = new ScriptEngineManager();
        ScriptEngine engine = mgr.getEngineByName("JavaScript");
        try {
            System.out.println(engine.eval("1+1"));
        } catch (ScriptException e) {
            e.printStackTrace();
        }
    }
}

// C++ doesn't have a built-in `eval` function. You would typically write a custom parser or use a library.

// C# has no direct `eval` function but can compile code at runtime using libraries like Roslyn
using Microsoft.CodeAnalysis.CSharp.Scripting;
using Microsoft.CodeAnalysis.Scripting;
using System;

class Program {
    static async Task Main() {
        try {
            var result = await CSharpScript.EvaluateAsync("1+1");
            Console.WriteLine(result);
        } catch (CompilationErrorException compilationError) {
            // Handle error
        }
    }
}

// Go doesn't have an `eval` equivalent. You would typically need to write a custom parser or use a third-party package.

Thinking Like a Compiler

We can't use the built-in eval method, but that's not going to stop us.

Let's put on our compiler hats and dissect this problem. Essentially, our job is to translate the language of mathematics into something the machine understands. Our plan involves two critical steps:

Step 1: Parsing the Expression

In this step, we're essentially acting as translators. We must walk through each character in the expression string and categorize it. Think of it as scanning a sentence and tagging each word as a noun, verb, or adjective. In our case, we have four types of "words" or symbols:

1. Integers: These are the numbers in our expression. We'll detect them and store their values for computation.
2. Signs/Operations: We're only concerned with addition and subtraction, represented by + and -.
3. Parentheses: These ( and ) symbols affect the order of operations.
4. Spaces: They can be ignored for our purpose but need to be identified nonetheless.

Step 2: Evaluating the Expression

Once we know what each symbol stands for, we can proceed to do the actual math. This is the part where we apply the rules of arithmetic to get our final answer.

Crafting a Strategy

Our roadmap seems pretty straightforward; however, there are some "watch out!" signs along the way. The devil is in the details—or in this case, the order and combination of these symbols.

A Simple Example: '1+1'

Let's use the simple expression 1+1 to illustrate our approach. Imagine a variable result that stores the outcome. Now, our logic could look like this:

1. Initialize result to 0.
2. Loop through each character in the string '1+1'.
3. Identify the character type:
   • If it's a number, add it to result.
   • If it's a +, continue adding to result.

Our logic flows naturally, but as we'll discover, more complex expressions will require a more nuanced approach.

public class Calculator {
    public static void main(String[] args) {
        String expression = "1+1";
        int result = 0;

        for (char c : expression.toCharArray()) {
            if (Character.isDigit(c)) {
                result += Character.getNumericValue(c);
            }
            // If it's a '+', we simply continue the loop
        }
        System.out.println("Result: " + result);
    }
}

const expression = "1+1";
let result = 0;

for (const char of expression) {
    if (!isNaN(char)) {
        result += Number(char);
    }
    // If it's a '+', we simply continue the loop
}
console.log("Result:", result);

expression = "1+1"
result = 0

for char in expression:
    if char.isnumeric():
        result += int(char)
    # If it's a '+', we simply continue the loop

print("Result:", result)

#include <iostream>
#include <cctype>

int main() {
    std::string expression = "1+1";
    int result = 0;

    for (char c : expression) {
        if (std::isdigit(c)) {
            result += c - '0';
        }
        // If it's a '+', we simply continue the loop
    }
    std::cout << "Result: " << result << std::endl;
}

using System;

class Program {
    static void Main() {
        string expression = "1+1";
        int result = 0;

        foreach (char c in expression) {
            if (Char.IsDigit(c)) {
                result += (int)Char.GetNumericValue(c);
            }
            // If it's a '+', we simply continue the loop
        }
        Console.WriteLine("Result: " + result);
    }
}

package main

import (
    "fmt"
    "unicode"
)

func main() {
    expression := "1+1"
    result := 0

    for _, char := range expression {
        if unicode.IsDigit(char) {
            result += int(char - '0')
        }
        // If it's a '+', we simply continue the loop
    }
    fmt.Println("Result:", result)
}

The Elegance of Addition

Addition is straightforward, isn't it? When we encounter a number in our expression string, we simply add it to our running total, which we'll call result. That's about it for addition.

Subtraction as "Negative Addition"

Here's where the subtlety comes in. Instead of thinking of subtraction as a separate operation, let's reframe it as adding a negative number. This concept simplifies our logic beautifully. Now, we don't have to juggle between two different operations; it's all addition!

A Practical Example: '1-1'

To illustrate how this works, let's consider the expression 1-1. Our logic could flow as follows:

1. Initialize result to 0.
2. Loop through each character in the string '1-1'.
3. Identify what each character is:
   • If it's a number, add it to result.
   • If it's a - sign, prepare to make the next number negative.

By following these steps, we'll add 1 to result, and then effectively add -1 to result, resulting in a final value of 0.

In the above example, we simply converted the signage when we encountered a minus symbol-- so we need to keep some concept of what sign we're at. This will allow us to keep track of what operation we're performing, whether it's + or -.

Assuming we handle signage with a 1 or a -1, our method so far starts to look something like this:

```java
public class Calculator {
    public static void main(String[] args) {
        System.out.println(calculator("4+4+(6-1)"));
    }

    public static int calculator(String str) {
        int result = 0, sign = 1;

        for (int i = 0; i < str.length(); i++) {
            char curr = str.charAt(i);
            if (curr == '+') {
                sign = 1;
            } else if (curr == '-') {
                sign = -1;
            } else if (curr >= '0' && curr <= '9') {
                StringBuilder num = new StringBuilder();
                num.append(curr);
                while (i + 1 < str.length() && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9') {
                    num.append(str.charAt(i + 1));
                    i++;
                }
                result += sign * Integer.parseInt(num.toString());
            }
        }
        return result;
    }
}
```
```javascript
function calculator(str) {
	let result = 0, sign = 1;
    
	for (let i = 0; i < str.length; i++) {
		const curr = str.charAt(i);
		if (curr === '+') {
			sign = 1;
		} else if (curr === '-') {
			sign = -1;
		} else if (curr >= '0' && curr <= '9') {
			let num = curr;
			while (i + 1 < str.length && str.charAt(i + 1) >= '0' && str.charAt(i + 1) <= '9') {
				num += str.charAt(i + 1);
				i++;
			}
            result += sign * parseInt(num);
        }
    }
    return result;
}
```
```python
def calculator(s):
    result = 0
    sign = 1

    i = 0
    while i < len(s):
        curr = s[i]
        if curr == "+":
            sign = 1
        elif curr == "-":
            sign = -1
        elif curr >= "0" and curr <= "9":
            num = curr
            while i + 1 < len(s) and s[i + 1] >= "0" and s[i + 1] <= "9":
                num += s[i + 1]
                i += 1
            result += sign * int(num)
        i += 1

    return result
```
```cpp
#include <iostream>
#include <string>

int calculator(std::string str) {
    int result = 0, sign = 1;

    for (int i = 0; i < str.length(); i++) {
        char curr = str[i];
        if (curr == '+') {
            sign = 1;
        } else if (curr == '-') {
            sign = -1;
        } else if (curr >= '0' && curr <= '9') {
            std::string num;
            num += curr;
            while (i + 1 < str.length() && str[i + 1] >= '0' && str[i + 1] <= '9') {
                num += str[i + 1];
                i++;
            }
            result += sign * std::stoi(num);
        }
    }
    return result;
}

int main() {
    std::cout << calculator("4+4+(6-1)") << std::endl;
}
```
```csharp
using System;

class Program {
    static void Main() {
        Console.WriteLine(calculator("4+4+(6-1)"));
    }

    static int calculator(string str) {
        int result = 0, sign = 1;

        for (int i = 0; i < str.Length; i++) {
            char curr = str[i];
            if (curr == '+') {
                sign = 1;
            } else if (curr == '-') {
                sign = -1;
            } else if (curr >= '0' && curr <= '9') {
                string num = curr.ToString();
                while (i + 1 < str.Length && str[i + 1] >= '0' && str[i + 1] <= '9') {
                    num += str[i + 1];
                    i++;
                }
                result += sign * Int32.Parse(num);
            }
        }
        return result;
    }
}
```
```go
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func calculator(str string) int {
	result := 0
	sign := 1

	for i := 0; i < len(str); i++ {
		curr := str[i]
		if curr == '+' {
			sign = 1
		} else if curr == '-' {
			sign = -1
		} else if curr >= '0' && curr <= '9' {
			var num strings.Builder
			num.WriteByte(curr)
			for i+1 < len(str) && str[i+1] >= '0' && str[i+1] <= '9' {
				num.WriteByte(str[i+1])
				i++
			}
			numInt, _ := strconv.Atoi(num.String())
			result += sign * numInt
		}
	}
	return result
}

func main() {
	fmt.Println(calculator("4+4+(6-1)"))
}
```

Parentheses

Parentheses serve a dual role: they dictate the order of operations, and in more complex scenarios, they could also signify multiplication. But we're ignoring multiplication for now. So, what's the big deal?

Why Are Parentheses Tricky?

Parentheses create a new "scope" for our calculations. Think of them like those Russian nesting dolls; what happens inside the innermost doll shouldn't affect the outer dolls directly. Parentheses introduce a hierarchical structure to the expression, which complicates our otherwise linear flow of calculations.

The Mighty Stack Data Structure

The classic way to handle this hierarchical structure is by using a stack. Imagine a stack of books; you can only add or remove a book from the top. Similarly, a stack in computer science is a data structure where you can add elements to the top and remove them from the top.

We'll use two stacks for our calculator:

1. Result Stack: To keep track of intermediate results.
2. Operation Stack: To store the sign (either + or -) before and within the parentheses.

Logic for Handling Parentheses

The stack will help us remember the result and sign right before we enter a new set of parentheses. When we close the parentheses, we can pop the top elements from our stacks to restore the previous state and correctly compute the result.

if (curr == '(') {
    stack.push(result);
    result = 0;
    operationStack.push(sign);
    sign = 1;
} else if (curr == ')') {
    result = operationStack.pop() * result + stack.pop();
    sign = 1;
}

if (curr === '(') {
  stack.push(result);
  result = 0;
  operationStack.push(sign);
  sign = 1;
} else if (curr === ')') {
  result = operationStack.pop() * result + stack.pop();
  sign = 1;
}

elif curr == "(":
    stack.append(result)
    result = 0
    operationStack.append(sign)
    sign = 1
elif curr == ")":
    result = operationStack.pop() * result + stack.pop()
    sign = 1

if (curr == '(') {
    stack.push(result);
    result = 0;
    operationStack.push(sign);
    sign = 1;
} else if (curr == ')') {
    result = operationStack.top() * result + stack.top();
    stack.pop();
    operationStack.pop();
    sign = 1;
}

if (curr == '(') {
    stack.Push(result);
    result = 0;
    operationStack.Push(sign);
    sign = 1;
} else if (curr == ')') {
    result = operationStack.Pop() * result + stack.Pop();
    sign = 1;
}

if curr == '(' {
    stack = append(stack, result)
    result = 0
    operationStack = append(operationStack, sign)
    sign = 1
} else if curr == ')' {
    osLen := len(operationStack)
    sLen := len(stack)
    result = operationStack[osLen-1]*result + stack[sLen-1]
    operationStack = operationStack[:osLen-1]
    stack = stack[:sLen-1]
    sign = 1
}

By using stacks to manage the state inside parentheses, we can effectively simplify our calculations while respecting the order of operations. So, are you ready to integrate this into our calculator code?

One final caveat-- we also need to handle spaces, but that's easy to accomplish by skipping that iteration.

if (curr == ' ') {
    continue;
}

if (curr === ' ') {
  continue;
}

if curr == " ":
    continue

if (curr == ' ') {
    continue;
}

if (curr == ' ') {
    continue;
}

if curr == ' ' {
    continue
}

Complexity of Final Solution

Let n be the length of the input. We iterate through the input once for O(n) time complexity, and we can have up to n elements on the stack (for example having an input only containing () for O(n) space complexity as well.

Let's see it all together now.

The Multiplication and Division Conundrum

So, you've mastered addition, subtraction, and those tricky parentheses. Feeling confident?

Now, let's up the ante with multiplication and division. This is often the follow-up question in interviews, and it adds an extra layer of complexity. Why? Because multiplication and division have higher precedence than addition and subtraction, and they introduce non-linear relationships between the numbers.

The Fundamental Question: Why Stacks?

The stack is a lifeline in this problem for one primary reason: it provides a way to handle different priorities of operations without needing to backtrack. Think of it as a holding area or a waiting room where numbers and operations can wait their turn to be processed in the correct sequence.

Why Does a Stack Work?

A stack works on a last-in, first-out (LIFO) principle. It allows us to temporarily "park" elements that we'll need soon but not immediately. In the case of multiplication and division, this "parking" facility becomes invaluable. It enables us to first collect the operands and then perform the operation when the time is right.

Mental Model with Example: "4 * 3 + 2"

Let's take an example expression: 4 * 3 + 2. There's no parentheses, so it's easier to follow. We'll use Python for this example.

Here's a step-by-step breakdown:

1. Initialization: We initialize num to 0, stack to an empty list, and sign to +.

num, stack, sign = 0, [], "+"

int num = 0;
Stack<Integer> stack = new Stack<>();
char sign = '+';

let [num, stack, sign] = [0, [], "+"];

int num = 0;
std::stack<int> stack;
char sign = '+';

int num = 0;
Stack<int> stack = new Stack<int>();
char sign = '+';

num, stack := 0, []int{}
sign := '+'

1. First Iteration (4):

   • We encounter 4, so num becomes 4.

2. Second Iteration (*):

   • We hit the *. At this point, the previous sign was +, so we push 4 onto stack.
   • We update sign to *.

3. Third Iteration (3):

   • We encounter 3, so num becomes 3.

4. Fourth Iteration (+):

   • We hit the +. The last sign was *, so we pop 4 from stack and push 4 * 3 = 12.
   • We update sign to +.

5. Fifth Iteration (2):

   • We encounter 2, so num becomes 2.

6. End of String:

   • The last sign is +, so we push 2 onto stack.

7. Final Calculation:

   • We sum the stack [12, 2], which results in 14.

```py
def calculator(s):
    num, stack, sign = 0, [], "+"

    for i in range(len(s)):
        # Check if it's a number
        # If there's a previous `num` (num is not 0),
        # it's multi-digit (ex. 13), so we extend it
        # while processing `3`
        if s[i].isnumeric():
            num = num * 10 + int(s[i])
        if s[i] in "+-*/" or i == len(s) - 1:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                # Our multiplication step: the stack.pop()
                # will provide the last number we encountered.
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))
            num = 0
            sign = s[i]
    return sum(stack)

print(calculator("4*3+2"))
```
```js
function calculator(s) {
    let [num, stack, sign] = [0, [], "+"]

    for (let i = 0; i < s.length; i++) {
        // Check if it's a number
        // If there's a previous `num` (num is not 0),
        // it's multi-digit (ex. 13), so we extend it
        // while processing `3`
        if (!isNaN(s[i])) {
            num = num * 10 + parseInt(s[i])
        }   
        if (["+", "-", "*", "/"].includes(s[i]) || i === s.length - 1) {
            console.log(i, s[i])
            if (sign == "+") {
                stack.push(num);
            } else if (sign == "-") {
                stack.push(-num);
            } else if (sign == "*") {
                // Our multiplication step: the stack.pop()
                // will provide the last number we encountered.
                stack.push(stack.pop() * num)                
            } else {
                // Division
                stack.push(parseInt(stack.pop() / num))
            }
            num = 0;
            sign = s[i];
        }
    }

    return stack.reduce((prev, curr) => { return prev + curr; }, 0)
}

console.log(calculator("4*3+2"))
```
```java
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        System.out.println(calculator("4*3+2"));
    }

    public static int calculator(String s) {
        int num = 0;
        Stack<Integer> stack = new Stack<>();
        char sign = '+';

        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if ("+-*/".indexOf(s.charAt(i)) != -1 || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else {
                    stack.push(stack.pop() / num);
                }
                num = 0;
                sign = s.charAt(i);
            }
        }
        return stack.stream().mapToInt(Integer::intValue).sum();
    }
}
```
```cpp
#include <iostream>
#include <stack>
#include <string>

int calculator(std::string s) {
    int num = 0;
    std::stack<int> stack;
    char sign = '+';
    
    for (int i = 0; i < s.length(); i++) {
        if (std::isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        }
        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.length() - 1) {
            if (sign == '+') {
                stack.push(num);
            } else if (sign == '-') {
                stack.push(-num);
            } else if (sign == '*') {
                int temp = stack.top();
                stack.pop();
                stack.push(temp * num);
            } else {
                int temp = stack.top();
                stack.pop();
                stack.push(temp / num);
            }
            num = 0;
            sign = s[i];
        }
    }

    int sum = 0;
    while (!stack.empty()) {
        sum += stack.top();
        stack.pop();
    }

    return sum;
}

int main() {
    std::cout << calculator("4*3+2") << std::endl;
    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        Console.WriteLine(Calculator("4*3+2"));
    }

    static int Calculator(string s) {
        int num = 0;
        Stack<int> stack = new Stack<int>();
        char sign = '+';

        for (int i = 0; i < s.Length; i++) {
            if (Char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if ("+-*/".IndexOf(s[i]) != -1 || i == s.Length - 1) {
                if (sign == '+') {
                    stack.Push(num);
                } else if (sign == '-') {
                    stack.Push(-num);
                } else if (sign == '*') {
                    stack.Push(stack.Pop() * num);
                } else {
                    stack.Push(stack.Pop() / num);
                }
                num = 0;
                sign = s[i];
            }
        }
        return stack.Sum();
    }
}
```
```go
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func calculator(s string) int {
	num, stack := 0, []int{}
	sign := '+'

	for i := 0; i < len(s); i++ {
		if s[i] >= '0' && s[i] <= '9' {
			num = num*10 + int(s[i]-'0')
		}
		if s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == len(s)-1 {
			if sign == '+' {
				stack = append(stack, num)
			} else if sign == '-' {
				stack = append(stack, -num)
			} else if sign == '*' {
				last := stack[len(stack)-1]
				stack[len(stack)-1] = last * num
			} else {
				last := stack[len(stack)-1]
				stack[len(stack)-1] = last / num
			}
			num = 0
			sign = rune(s[i])
		}
	}

	sum := 0
	for _, val := range stack {
		sum += val
	}
	return sum
}

func main() {
	fmt.Println(calculator("4*3+2"))
}
```

Multiplication and Division with Parentheses

We've been focusing on adding and subtracting, but now let's tackle multiplication and division when they're tossed into the mix with parentheses. The challenge is to keep processing our string expression from left to right while still honoring the parentheses and the order of operations. So, let's rethink our approach a bit.

The "Aha" Moment: View Multiplication as Extended Addition

Imagine you're staring at the expression "4*(3+2)". We naturally get drawn to the parentheses and think about tackling that first. But what if we reframe it? Instead of seeing it as "4 multiplies (3+2)", think of it as "0 add (4 * 5)".

Why the Reframe Works

This reframe works because it turns a nested operation into a linear one. The operation that seemed nested within the parentheses is now another operation in the queue. And because we've flattened it out, we can handle it with a left-to-right pass through the string, just like we did with simpler expressions.

Leveraging the Stack for this Reframe

The stack data structure comes to our rescue here. As we go through the string, we keep track of numbers and operations, as usual. But now, when we encounter a parenthesis, we use the stack to "remember" the operation that was happening right before we dove into the parenthesis. This enables us to "flatten" the nested operation into a linear one.

if ch == "(":
    # We can still leverage the stack that we're using
    # by recreating the parentheses expression within the stack
    stack.append(sign)
    stack.append('(')
    # Reset to plus to add the parentheses expression results
    sign = '+'

Unpacking the Parentheses

When we exit the parenthesis, we unpack the operations and numbers we've stored and perform the calculation. This way, the result of "3+2" in "4*(3+2)" becomes just another number in our queue of operations.

if ch == ')':
    # Complete our parentheses expression 
    num, item = 0, stack.pop()
    while item != '(':
        num += item
        item = stack.pop()
    sign = stack.pop()

Python: Implementing the Strategy

In Python, let's walk through the code step-by-step:

1. Initialize Variables: We start by initializing our variables. The variable num will hold the number we're currently parsing, stack will hold our numbers and signs, and sign will hold the current operation (addition by default).

   num, stack, sign = 0, [], "+"
   

2. Loop Through the String: We'll loop through each character in the string. For the last iteration, we append a '+' to ensure we process all numbers.

   for i, ch in enumerate(s + '+'):
   

3. Detect Numbers: If the character is numeric, we build the current number.

   if ch.isnumeric():
       num = num * 10 + int(ch)
   

4. Handling Parentheses: When we encounter an open parenthesis, we push the current sign and parenthesis to the stack, and then reset sign to '+'.

   if ch == "(":
       stack.append(sign)
       stack.append('(')
       sign = '+'
   

5. Handle Operations and Close Parenthesis: When we encounter any operator or close parenthesis, we perform the respective operation.

   if ch in "+-*/)" or i == len(s) - 1:
       if sign == "+":
           stack.append(num)
       elif sign == "-":
           stack.append(-num)
       elif sign == "*":
           stack.append(stack.pop() * num)
       elif sign == '/':
           stack.append(int(stack.pop() / num))
   

6. Close Parenthesis Logic: If we encounter a close parenthesis, we process the numbers within the parenthesis and sum them up.

   if ch == ')':
       num, item = 0, stack.pop()
       while item != '(':
           num += item
           item = stack.pop()
       sign = stack.pop()
   

7. Reset for Next Loop: Finally, we reset num and sign for the next iteration.

   else:
       num = 0
       sign = ch
   

8. Sum it Up: At the end, our stack will contain the numbers we need to sum to get the answer.

   return sum(stack)
   

9. Test the Function: We'll use an example to test our function.

   print(calculator("4*(3+2)"))  # Output should be 20
   

```py
def calculator(s):
    num, stack, sign = 0, [], "+"

    # Numerate through string and a '+' to loop far enough
    for i, ch in enumerate(s + '+'):
        # Check if it's a number
        # If there's a previous `num` (num is not 0),
        # it's multi-digit (ex. 13), so we extend it
        # while processing `3`
        if ch.isnumeric():
            num = num * 10 + int(ch)
        if ch == "(":
            # We can take still leverage the stack that we're using
            # by recreating the parentheses expression within the stack
            stack.append(sign)
            stack.append('(')
            # Reset to plus to add the parentheses expression results
            sign = '+'
        if ch in "+-*/)" or i == len(s) - 1:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                # Our multiplication step: the stack.pop()
                # will provide the last number we encountered.
                stack.append(stack.pop() * num)
            elif sign == '/':
                stack.append(int(stack.pop() / num))
            if ch == ')':
                # Complete our parentheses expression 
                num, item = 0, stack.pop()
                while item != '(':
                    num += item
                    item = stack.pop()
                sign = stack.pop()
            else:
                num = 0
                sign = ch
    return sum(stack)

print(calculator("4*(3+2)"))
```
```javascript
function calculator(s) {
    let [num, stack, sign] = [0, [], "+"];
    s += '+';
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (!isNaN(ch)) {
            num = num * 10 + parseInt(ch);
        }
        if (ch === "(") {
            stack.push(sign);
            stack.push('(');
            sign = '+';
        }
        if ("+-*/)".includes(ch) || i === s.length - 1) {
            if (sign === "+") {
                stack.push(num);
            } else if (sign === "-") {
                stack.push(-num);
            } else if (sign === "*") {
                stack.push(stack.pop() * num);
            } else {
                stack.push(parseInt(stack.pop() / num));
            }
            if (ch === ')') {
                num = 0;
                let item = stack.pop();
                while (item !== '(') {
                    num += item;
                    item = stack.pop();
                }
                sign = stack.pop();
            } else {
                num = 0;
                sign = ch;
            }
        }
    }
    return stack.reduce((prev, curr) => prev + curr, 0);
}

console.log(calculator("4*(3+2)"));
```
```java
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        System.out.println(calculator("4*(3+2)"));
    }

    public static int calculator(String s) {
        int num = 0;
        Stack<Integer> stack = new Stack<>();
        char sign = '+';
        s += '+';
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            if ("+-*/)".indexOf(ch) != -1 || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else {
                    stack.push(stack.pop() / num);
                }
                if (ch == ')') {
                    num = 0;
                    int item = stack.pop();
                    while (item != Integer.MIN_VALUE) {
                        num += item;
                        item = stack.pop();
                    }
                    sign = (char) stack.pop().intValue();
                } else {
                    num = 0;
                    sign = ch;
                }
            }
            if (ch == '(') {
                stack.push((int) sign);
                stack.push(Integer.MIN_VALUE);
                sign = '+';
            }
        }
        return stack.stream().mapToInt(Integer::intValue).sum();
    }
}
```
```cpp
#include <iostream>
#include <stack>
#include <string>
#include <numeric>
using namespace std;

int calculator(string s) {
    int num = 0;
    stack<int> stack;
    char sign = '+';
    s += '+';
    for (int i = 0; i < s.length(); i++) {
        char ch = s[i];
        if (isdigit(ch)) {
            num = num * 10 + (ch - '0');
        }
        if (string("+-*/)").find(ch) != string::npos || i == s.length() - 1) {
            if (sign == '+') {
                stack.push(num);
            } else if (sign == '-') {
                stack.push(-num);
            } else if (sign == '*') {
                int top = stack.top();
                stack.pop();
                stack.push(top * num);
            } else {
                int top = stack.top();
                stack.pop();
                stack.push(top / num);
            }
            if (ch == ')') {
                num = 0;
                int item = stack.top();
                stack.pop();
                while (item != INT_MIN) {
                    num += item;
                    item = stack.top();
                    stack.pop();
                }
                sign = stack.top();
                stack.pop();
            } else {
                num = 0;
                sign = ch;
            }
        }
        if (ch == '(') {
            stack.push(sign);
            stack.push(INT_MIN);
            sign = '+';
        }
    }
    return accumulate(stack.begin(), stack.end(), 0);
}

int main() {
    cout << calculator("4*(3+2)") << endl;
    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        Console.WriteLine(Calculator("4*(3+2)"));
    }

    static int Calculator(string s) {
        int num = 0;
        Stack<int> stack = new Stack<int>();
        char sign = '+';
        s += '+';
        for (int i = 0; i < s.Length; i++) {
            char ch = s[i];
            if (Char.IsDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            if ("+-*/)".Contains(ch) || i == s.Length - 1) {
                if (sign == '+') {
                    stack.Push(num);
                } else if (sign == '-') {
                    stack.Push(-num);
                } else if (sign == '*') {
                    stack.Push(stack.Pop() * num);
                } else {
                    stack.Push(stack.Pop() / num);
                }
                if (ch == ')') {
                    num = 0;
                    int item = stack.Pop();
                    while (item != Int32.MinValue) {
                        num += item;
                        item = stack.Pop();
                    }
                    sign = (char)stack.Pop();
                } else {
                    num = 0;
                    sign = ch;
                }
            }
            if (ch == '(') {
                stack.Push(sign);
                stack.Push(Int32.MinValue);
                sign = '+';
            }
        }
        return stack.Sum();
    }
}
```

One Pager Cheat Sheet

• Let's program a very basic calculator, handling positive, negative symbols, parentheses, and spaces, without using eval function!
• In most languages, you can evaluate code strings quickly and easily using eval.
• We can break down the problem into parsing and evaluating symbols such as integers, signs/operations, parenthesis and spaces, and iterate through an expression string to transform it into a form understandable by the machine, with some caveats in the processing order.
• Adding a negative number to our running result is the key to solving the problem of subtraction.
• We can keep track of our sign while converting the signs of numbers by using 1 or -1 to represent the + or - operations respectively.
• Leveraging two stacks to keep track of the result and operations within the parentheses is the key to solving this challenging problem.
• We skip that iteration if the current character is a space.
• We can iterate through the input of length n in O(n) time and space complexity.
• We can extend our previous solution to handle Multiplication and Division by using a stack to store multipliers and dividers and multiplying or dividing the result of each for loop iteration by this stack as it pops values off.
• Byrecreatingthe parentheses expression on a stack, we can still use the left-to-right approach to parse"4*(3+2)", instead of being "drawn to the parentheses".