LeetCode 227: Basic Calculator II

Problem

LeetCode 227: Basic Calculator II (Medium)

Problem statement: Evaluate a valid arithmetic expression containing only numbers, spaces, and the operators +, -, *, and /.

This is almost as simple as an arithmetic expression evaluator can be. It’s simpler than the first Basic Calculator problem, which includes parentheses. The only trick in this version is respecting the order of operations, which in this case is just MDAS since there are no parentheses or exponents.

This solution variation doesn’t use a stack, so it relies on processing the input string character by character (one pass) and setting each variable at the correct point in the process.

Solution

This solution is based on the official LeetCode solution (available without a subscription), Approach 2: Optimized approach without the stack.

Variables

• s: The input string
• i: The position in the input string. We need to know the position because there’s a special case for the last character.
• c: The current character in the input string. Each character is either a digit or an operator.
• result: The final result. This variable also stores the intermediate result after an addition or subtraction operation, but is unchanged after a multiplication or division operation.
• num: An integer operand from the input string.
• prev: After a multiplication or division operation, this stores the intermediate (previous) result. After an addition or subtraction operation, it is initialized to the current num (or -num) value, so it can be used in an upcoming multiplication or division.
• op: The most recent operator, set at the end of the previous iteration. It is initialized to +, since the first operand is always positive.

Algorithm

• Remove all spaces from the input string s, so the only remaining characters are digits and operators.
• Process each character c of s.
• If c is a digit, append it to the current integer operand, num.
• If c is not a digit or c is the last character in s, do the steps below. The “last character” special case is required because the input string doesn’t contain an “evaluate expression” operator like =.

Evaluation steps:

• op always contains the current operator: + when the program starts, or the most recent operator seen in the input.
• If op is + or -, add prev to result. This is equivalent to popping any pending multiplication or division operation in the stack version of this algorithm. Then set prev to num if op is + or -num if op is -. This sets the intermediate result that any future operations will operate on.
• If op is *, multiply prev (the intermediate result) by num (the next operand).
• If op is /, divide prev (the intermediate result) by num (the next operand).
• Set op (the next operation) to c.
• Set num to 0 so we start with a fresh number when we encounter the next digit.

Pseudocode

remove all spaces from s
for each char c in input string
    if c is a digit, append it to num
    if c is not a digit or c is the last character in s
        if op is + or -
            add prev to result
            if op is +, set prev to num
            else set prev to -num
        if op is *, multiply prev by num
        if op is /, divide prev by num
        op = c
        num = 0
add prev to result
return result

Code

Basic Calculator II on GitHub.

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.