Solution: Basic Calculator

Statement#

Given a string containing an arithmetic expression, implement a basic calculator that evaluates the expression string. The expression string can contain integer numeric values and should be able to handle the “+” and “-” operators, as well as “()” parentheses.

Constraints:

Let s be the expression string. We can assume the following constraints:

• $1 \leq$ s.length $\leq 3 \times 10^{4}$
• s consists of digits, “+”, “-”, “(”, and “)”.
• s represents a valid expression.
• “+” is not used as a unary operation ( $+1$ and $+(2 + 3)$ are invalid).
• “-” could be used as a unary operation ($-1$ and $-(2 + 3)$ are valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

Pattern: Stacks#

While calculating the arithmetic expression, we evaluate the individual subexpressions. We need to store the results of these intermediate calculations in place of those subexpressions. Then we’ll need to get back the most recent stored result.

A feature of this problem is that subexpressions can be nested, one within another. This arrangement can be easily mimicked during the evaluation of these subexpressions by pushing them to the stack and then popping them as we return from nesting. So these operations can be performed using the basic methods of the stack—that is, push and pop.

Solution#

The slides below illustrate how we’d like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Let’s start with the simplest step—we’ll iterate the whole expression character by character. If a digit is found, we need to form the operand by multiplying the previously formed operand by $10$ and adding the current digit to it. If we encounter any other operator, we’ll simply reset the variable.

The highlighted lines implement this logic:

When we encounter the “+” or “-” operators, we first evaluate the expression to the left and save the sign value for the next evaluation (lines 32–37):

If “(” is found, we push the result calculated so far and the sign value onto the stack (lines 37–46):

If “)” is found, we’ll perform two tasks:

• We’ll calculate the expression to the left. The result of this would be the result of the expression within the set of parenthesis that just ended.

• Pop the sign value from the top of the stack (that we stored before starting the open parenthesis) and multiply it with the computed result within the parenthesis. Then we’ll pop the previously stored result from the stack and add it with the result of parenthesis.

The highlighted lines implement this logic:

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following four parts:

• Store the consecutive digits.
• On detecting “+” or “-”, evaluate the left expression and store the new sign value.
• On detecting “(”, push the result calculated until now and store the sign value
• On detecting “)”, convert the current number to be positive or negative if we need to perform an addition or a subtraction respectively, and add it to the previously calculated result.

Time complexity#

Since we are only traversing the string once, the time complexity of the algorithm above is $O(n)$, where $n$ is the length of the string.

Space complexity#

The space complexity is $O(n)$ in the worst case, where most of the expression is a series of nested sub-expressions.