## 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.*