Problem Explanation

We need to build a basic calculator which will evaluate a given expression string. This string might contain parentheses "()" , plus "+" or minus "-" signs , non-negative integers and empty spaces " " . The given expression will always be valid and eval built-in library function will not be used to solve the problem. The function will then return the calculated value of the expression.

For example, if the input is "1 + 1", the output will be 2. If the input is "(1+(4+5+2)-3)+(6+8)", the output will be 23.

Approach

To approach this problem, we will use the concept of Stack data structure and evaluate the expression. We will have a variable 'sign' which will hold the value of the current sign and if we encounter a sign, we will add the current number and num to the answer. num will always store the latest number. So if the current character is a digit, we will update num. If the character is (, we will push the currentsignin the stack. If the character is), we will pop the stack and if the character is +or- we will addsign*numtoans, update the sign, reset num, update signas top of stack * currentsign(+is 1 and-` is -1)

Let's understand it with an example

For example "2-1 + 2" Here we start with initial values ans=0 and num=0 and sign=1. We start our scanning from the left. So, the first digit is 2, so num=2. The next digit we encounter is "-", so we add sign*num to ans i.e 2 to the ans so ans=2, we encountered a - so sign = -1 * 1 = -1, then we see a 1 hence num=1, the next character we see is + so ans = ans + sign*num = 2 - 1 = 1 , we encountered a + so sign = 1 * 1 = 1 , we see a 2 so num=2. Finally when we reach the end ans = ans + sign * num = 1 + 1 * 2 = 3

Solution

Python

1
2py
3class Solution:
4    def calculate(self, s):
5        ans = 0
6        num = 0
7        sign = 1
8        stack = [1]  # Stack is initially 1
9
10        for c in s:
11            if c.isdigit():
12                num = num * 10 + int(c)
13            elif c == '(':
14                stack.append(sign)
15            elif c == ')':
16                stack.pop()
17            elif c == '+' or c == '-':
18                ans += sign * num
19                sign = (1 if c == '+' else -1) * stack[-1]  # Update the sign
20                num = 0
21
22        return ans + sign * num

Java

1
2java
3class Solution {
4    public int calculate(String s) {
5        int ans = 0;
6        int num = 0;
7        int sign = 1;
8        Stack<Integer> stack = new Stack<>();
9        stack.push(sign);
10
11        for (char c : s.toCharArray()) {
12            if (Character.isDigit(c)) {
13                num = num * 10 + (c - '0');
14            } else if (c == '(') {
15                stack.push(sign);
16            } else if (c == ')') {
17                stack.pop();
18            } else if (c == '+' || c == '-') {
19                ans += sign * num;
20                sign = (c == '+' ? 1 : -1) * stack.peek();
21                num = 0;
22            }
23        }
24
25        return ans + sign * num;
26    }
27}

JavaScript

1
2js
3class Solution {
4    calculate(s) {
5        let ans = 0, num = 0, sign = 1, stack = [1];
6
7        for (let c of s) {
8            if (/\d/.test(c)) {
9                num = num * 10 + Number(c);
10            } else if (c === '(') {
11                stack.push(sign);
12            } else if (c === ')') {
13                stack.pop();
14            } else if (c === '+' || c === '-') {
15                ans += sign * num;
16                sign = (c === '+' ? 1 : -1) * stack[stack.length - 1];
17                num = 0;
18            }
19        }
20
21        return ans + sign * num;
22    }
23}

C++

1
2cpp
3class Solution {
4public:
5    int calculate(string s) {
6        int ans = 0, num = 0, sign = 1;
7        stack<int> stack;
8        stack.push(sign);
9
10        for (char c : s) {
11            if (isdigit(c)) {
12                num = num * 10 + (c - '0');
13            } else if (c == '(') {
14                stack.push(sign);
15            } else if (c == ')') {
16                stack.pop();
17            } else if (c == '+' || c == '-') {
18                ans += sign * num;
19                sign = (c == '+' ? 1 : -1) * stack.top();
20                num = 0;
21            }
22        }
23
24        return ans + sign * num;
25    }
26};

C#

1
2csharp
3public class Solution {
4    public int Calculate(string s) {
5        int ans = 0, num = 0, sign = 1;
6        Stack<int> stack = new Stack<int>();
7        stack.Push(sign);
8        
9        foreach (char c in s) {
10            if (Char.IsDigit(c)) {
11                num = num * 10 + (c - '0');
12            } else if (c == '(') {
13                stack.Push(sign);
14            } else if (c == ')') {
15                stack.Pop();
16            } else if (c == '+' || c == '-') {
17                ans += sign * num;
18                sign = (c == '+' ? 1 : -1) * stack.Peek();
19                num = 0;
20            }
21        }
22        
23        return ans + sign * num;
24    }
25}

Conclusion

The above explained and provided solution in Python, JavaScript, Java, C++ and C# will correctly calculate the value of an input expression in accordance with the standard order of operations. This solution is unique in addressing the embedded parentheses, taking them into account when performing computations. The use of the stack data structure is key here, as it enables us to handle the nested operations in an efficient and structured way. In addition, converting the input string into individual characters and processing them sequentially allows the program to handle different sized numbers and complex expressions seamlessly.

The solution overall has a time complexity of O(n), where n is the length of the string. This is because each character in the string is processed exactly once, resulting in linear time complexity.

In conclusion, this calculator program brilliantly highlights the proper usage and capabilities of data structures and control flow in tackling complex operations. It's a great example of how to solve problems using the fundamental concepts of computer science and programming.