Build a Calculator (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Microsoft, Google, Salesforce, Dropbox, Tableau Software, Yelp, Uber, Visa, Walmart Labs, Rubrik, Asana, Blend, Riot Games, and Proofpoint.

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?

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

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

1let expr = "3 - 1 + 2";
2calculator(expr)
3// 4
4
5expr = "(2+(4+2)-1)-(5+8)"
6calculator(expr)
7// -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)