Basic Calculator 2

 I always wondered about how to parse and execute complex numeric expressions, even though i did that my programming language agaram , i did that in a very different way ( using recursion ). So the problem statement here wants us to implement a program which parses the numeric expression. The expression consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces and they guarantee that the expression would be valid. 

 

The problem statement doesn't look complicated until you see this test case

3+2*2 

The expected output is 7. You would already know whats stopping us from mindlessly executing operations on series.

 

Its MATHS, well technically not maths. Its just that entire civilization accepted BODMAS  as the standard. Unless you plan to run in to woods and never be seen again, you are forced to adhere to this standard. Lets understand the cost we have to pay for co-existing with the civilization. BODMAS represents

B = Brackets

O = Orders ( exponents  )

D = Division

M = Multiplication

A = Addition

S = Subtraction

The issue here is we would need to perform division and multiplication as soon as we encounter the numbers.

Intuition:

My first idea here is if we perform multiplication and division operations on the first iteration, then on the second we could directly just sum up the values.

Lets take the expression.

3+2*2

in the first iteration we could turn this in to

3 + 4

Then on the next we could just add all the integers. The question is how we are going to do it, lets get in to technical details. The given input is a string, we would read it character by character. When we encounter a multiplication character then we just get the previous number, multiply it and put it back on the expression. 

If we encounter any operator -, + we just append that operator to next number.

To perform this operation we need two things

1. The previous number

2. The next number

But there is an issue here, the next number is not a single digit integer, there could be multi digit integer. Lets think about this test case

3 + 2 * 30

the output would be 63, the only technical issue is we need to consume numbers after operator to form the next number. On the first glance it doesnt seem to much of the problem. But we would need to implement this also for multiplication. To get the previous number in minimum amount of time, we can use a stack. To build the number from string, i am also going to use this trick

Note: Remember to ignore the spaces

 

First iteration:

last_num = 0

for c in s:

if c.is_numeric():

last_num = last_num * 10 + int(c)

 

No we need to decide when to push this number to our storage.  I guess the most reasonable think to do is perform that inside our c.is_numeric() because if we do it in else loop we would do that several times when we encounter space or other operators. To do that inside our if clause we can do a lookup and check if next character is not a number. But deciding to look one character after the current one brings us to another problem. We cant take for granted that next character would exist, because we might be in the end of string. So also need to make a check that if we are with in the bounds

class Solution:

def calculate(self, s: str) -> int:

stack = []

LEN = len(s)

last_num = 0

for i, c in enumerate(s):

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

stack.append(last_num)

else:

last_num = 0

print(stack)

return -1

The above code should be able to parse all the numbers and store it in list in order.

Notice that i == LEN - 1, this handles the case where we have an integer at last position. Before we put in the number to stack we would need to set the sign if the previous operator is + or -  ( why? because we decided to sum up the values in the end ), So if the expression is

2 + 3 - 4, then our list should be [ 2, 3, -4 ], this can be achieved with the below code

class Solution:

def calculate(self, s: str) -> int:

stack = []

LEN = len(s)

last_num = 0

last_sign = 1

for i, c in enumerate(s):

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

stack.append( last_sign * last_num)

else:

last_num = 0

if c == '+':

last_sign = 1

elif c == '-':

last_sign = -1

print(stack)

return -1

Note: Instead of keeping operators as string and then parsing it , i decided to use +1, -1 because it makes it much simple which trying to push the element to stack.

This works correctly, now all we need to do is implement our multiplication and division operator. In our intuition we said that once we encounter a division or mul operator we are going to need previous and next number. The issue with getting next number in our code is we need to parse the number, ignore the space etc. To avoid going in to complication, when we encounter multiplication or division operator we push it to stack.

Why am i pushing the operators to stack ?

I said that once we encounter division/mul operator we are going to need previous and next numbers. We are going to do the same except when we finish parsing a number we check if there is an operator at top of stack.

Since we are pushing only division and multiplication, we can take that operator out and previous number from it. By this way we dont need to duplicate the parsing logic.

class Solution:

def calculate(self, s: str) -> int:

stack, LEN, last_num, last_sign, i = [], len(s), 0, 1, 0

for i in range(LEN):

c = s[i]

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

# check if a operator is at the top of stack.

if len(stack) == 0 or stack[-1] not in ['*', '/']:

stack.append( last_sign * last_num)

else:

# we have the operator, lets take it out

next_number = last_sign * last_num

operator = stack.pop()

prev_number = stack.pop()

if operator == '*':

stack.append(prev_number * next_number)

elif operator == '/':

stack.append( prev_number // next_number )

else:

last_num = 0

if c == '+':

last_sign = 1

elif c == '-':

last_sign = -1

elif c in ['*', '/']:

stack.append(c)

print(stack)

return -1

This works as expected.

now all we need to do is to sum it up, i did that

class Solution:

def calculate(self, s: str) -> int:

stack, LEN, last_num, last_sign, i = [], len(s), 0, 1, 0

for i in range(LEN):

c = s[i]

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

# check if a operator is at the top of stack.

if len(stack) == 0 or stack[-1] not in ['*', '/']:

stack.append( last_sign * last_num)

else:

# we have the operator, lets take it out

next_number = last_sign * last_num

operator = stack.pop()

prev_number = stack.pop()

if operator == '*':

stack.append(prev_number * next_number)

elif operator == '/':

stack.append( prev_number // next_number )

else:

last_num = 0

if c == '+':

last_sign = 1

elif c == '-':

last_sign = -1

elif c in ['*', '/']:

stack.append(c)

print(stack)

return sum(stack)

and it failed for this test case

"12-3*4"

I was wondering why it failed, i mean we would have [12, -12] which will lead to 0, but it returned 24, then i realised i didnt reset the sign after adding the element to stack. I did that

class Solution:

def calculate(self, s: str) -> int:

stack, LEN, last_num, last_sign, i = [], len(s), 0, 1, 0

for i in range(LEN):

c = s[i]

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

# check if a operator is at the top of stack.

if len(stack) == 0 or stack[-1] not in ['*', '/']:

stack.append( last_sign * last_num)

else:

# we have the operator, lets take it out

next_number = last_sign * last_num

operator = stack.pop()

prev_number = stack.pop()

if operator == '*':

stack.append(prev_number * next_number)

elif operator == '/':

stack.append( prev_number // next_number )

last_sign = 1 # reset sign, dont forget to do this.

else:

last_num = 0

if c == '+':

last_sign = 1

elif c == '-':

last_sign = -1

elif c in ['*', '/']:

stack.append(c)

return sum(stack)

now its failing for "14-3/2"

it yields 12 instead of 13, now i  thought this might be due to division in python. Indeed it was. The `//` operator has a special case, when there are two positive integers it rounds towards positive infinity. If the result is negative it round towards the negative infinity hence it leads to our issue.

To avoid this complication we can just do int(a/b)

class Solution:

def calculate(self, s: str) -> int:

stack, LEN, last_num, last_sign, i = [], len(s), 0, 1, 0

for i in range(LEN):

c = s[i]

if c.isnumeric():

last_num = last_num * 10 + int(c)

if (i + 1 < LEN and not s[i+1].isnumeric()) or i == LEN - 1:

# check if a operator is at the top of stack.

if len(stack) == 0 or stack[-1] not in ['*', '/']:

stack.append( last_sign * last_num)

else:

# we have the operator, lets take it out

next_number = last_sign * last_num

operator = stack.pop()

prev_number = stack.pop()

if operator == '*':

stack.append(prev_number * next_number)

elif operator == '/':

stack.append(int(prev_number / next_number )) # dont use //

last_sign = 1

else:

last_num = 0

if c == '+':

last_sign = 1

elif c == '-':

last_sign = -1

elif c in ['*', '/']:

stack.append(c)

return sum(stack)

Lessons learned

1. Dont forget to reset the sign after pushing the element to stack

2. Dont use a//b for negative division, use int(a/b)