Feature #2: Evaluate the Arithmetic Expression

Description

For this feature, you have to create a module for evaluating mathematical expressions. The expressions are already extracted from the source code and are available as strings. Your job is to compute the result and return it. The expressions are subject to the following constraints:

• The numbers can only be integers.
• For simplicity’s sake, the expressions can only contain + and - operators.
• The expression can contain () parentheses.
• The expression has already been verified as being valid.

Let’s look at an example to understand the feature specifications. Suppose the input expression is "5-(3+4)". Your program has to evaluate it following mathematical rules. First, the expression inside parentheses is solved and then the rest. The result will be the integer value -2.

Solution

This problem is a great candidate for a stack use case. But first, we need to keep in mind the rules of addition and subtraction, the precedence of parentheses, and that the spaces in the string do not affect the output. We can use the stack to solve for the precedence of parentheses. If an expression contains an opening bracket (, we will push the elements into the stack until a closing bracket ) is found. Then, we will pop the elements and evaluate the sub-expression inside the brackets until the opening bracket (. However, when we calculate the final answer, we process the values from right to left, whereas it should be from left to right. The following slides illustrate this issue:

The example above shows how the string is reversed using the stack, and we will end up evaluating the expression in reverse order. Let’s look at a way to solve this problem.

We can use the - operator as the magnitude for the operand to the right of the operator. By using - as the magnitude for the operands, we will have only the addition operator left, ...