Basic Calculator II — LC Medium (hard)

Companies: Facebook, Amazon, Apple

227. Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Example 2:

Example 3:

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

My first approach: using Stacks

Approach needs explanation.

we start reading this string from left to right, check if the character is a digit or a character (could be operators or spaces) and whenever we meet number, we put it into stack.

When we meet an operator, we check if the calculation priority should be considered (that is, whenever we need multiplication or division, we need to compute those numbers first and perform any addition or substraction afterwards). luckily, we don’t really have any parentheses so we don’t have to worry about that.

its easier to explain with the test cases and going through the process one by one.

E.g.) “(space)22–3*5(space)”

base Operator : “+”

1st char: space, so we ignore it

2st char: 2, we store this info and see if there is any more subsequent numbers followed by it

3rd char: 2, we merge this with the 2nd char to make 22

4th char: “-”, this is the time when we meet our first operator {+, -, *, /} we store the 22 to our stack (stack: [22]). and since the base operator was “+”, we store (+22). now the operator changed to “-”.

5th char: 3, we check the last operator, since it was negative, we store -3 to stack (stack:[22, -3])

6th char: “*” change of operator, we don’t store any number yet.

7th char: 5, and the last operator was “*”, we pop the last entered element from the stack, multiply the 5 with -3, make it to -15, and store this -15 to stack (stack:[22, -15])

8th char: space, so we ignore it

at the end of the iteration, we have stack: [22, -15] and we just sum them as our final output.

code is as follows:

Time complexity: O(N)

Space complexity: O(N)

My second approach: optimized version of the first approach, basically without using stacks.

lets bring the first example E.g.) “(space)22–3*5(space)”

instead of storing the numbers to the stack, we make another pointer called “previous” and store the previous number and make this act like a stack.

base operator: “+”

current number: 0, previous number = 0, index = 0, temp = ‘’, result = 0

1st char: space, so we ignore it, idx += 1

2nd char: 2, idx += 1, temp = ‘2’

3rd char: 2, idx += 1, temp = ‘22’ and the next index is a negative; previous operator = “+”, we store 22 to our previous number and do previous operation to the resulting variable, which is 0 + 22 = 22

4th char: “-”, change the operator to “-”

5th char: 3, we compute 22–3 = 19 as our result so far, and previous number is now stored as -3

6th char: “*”, change the operator to “*”

7th char: 5, and previous operator was “*”, we first minus our previous number from the current result and compute the previous number * current number (that is, from 19 — (-3) = 22, and prev*cur = -3*5 = -15) and add it to the result: 22–15 = 7

8th char: space, so we ignore it

code is as follows:

Time complexity: O(N)

Space complexity: O(1)

--

--

Data Scientist, SWE + MLE

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store