Aline and Ray
Milan, IT
Two geeks in love with Open Source, programming and one another
A week ago, I did an interview for an R&D position in a company. Apart from some other technical and logical tasks, I was asked to implement a simple rpn calculator, with the basic operators: sum, subtraction, product, division and square root. For those who don’t know what an rpn is follows a brief description from the beginning.
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands - “infixed operators” - such as the plus sign in 2+2. So, in general this is the notation all of us know because is the one taught in school. In infix notation, unlike in prefix or postfix notations, parentheses surrounding groups of operands and operators are necessary to indicate the intended order in which operations are to be performed. In the absence of parentheses, certain precedence rules determine the order of operations. Reference
Also known as Polish prefix notation is a a mathematical notation in which operators precede their operands. It does not need any parentheses as long as each operator has a fixed number of operands.
So, given the following expression in infix notation (5 − 6) × 7 its corresponding PN is × (− 5 6) 7. Assuming a given arity of all involved operators (here the “−” denotes the binary operation of subtraction, not the unary function of sign-change), any well formed prefix representation thereof is unambiguous, and brackets within the prefix expression are unnecessary. As such, the above expression can be further simplified to × − 5 6 7. Reference
Also known as Polish postfix notation or simply postfix notation, RPN is a mathematical notation in which operators follow their operands, in contrast to the previously described Polish notation. So, the previous expression should be 7 6 5 − ×. Reference
This explanation is short but clear to understand the rest of this article. During the interview I was facing this problem, the rpn calculator and below you can find the solution I have wrote and then commented with the recruiter.
arr = [1, 7, 3, '/', 1, 4, '-', 2, '*', '/', '+']
arr_copy = arr[:]
def get_number_of_args(func):
""" Computes the number of arguments of a given function.
:returns: number of arguments of a given function
:rtype: int
"""
variables = list(func.__code__.co_varnames)
return len(variables)
def func_sum(a,b):
""" Computes the sum between the two variables.
:returns: sum between a and b
:rtype: int
"""
return a + b
def func_sub(a,b):
""" Computes the subtraction between the two variables.
:returns: subtraction between a and b
:rtype: int
"""
return a - b
def func_mul(a,b):
""" Computes the multiplication between the two variables.
:returns: multiplication between a and b
:rtype: int
"""
return a * b
def func_div(a,b):
""" Computes the division between the two variables.
:returns: division between a and b
:rtype: int
"""
return float(a) / b
def func_sqrt(a):
""" Computes the square root of a.
:returns: square root of a
:rtype: int
"""
return math.sqrt(a)
# Mapping between the operator and the function that calculates the result
operators = {
'+': func_sum,
'-': func_sub,
'*': func_mul,
'/': func_div,
'sqrt': func_sqrt
}
def calc():
""" Computes the result of the expression in arr.
:returns: None
"""
i = 0
while len(arr) != 1:
if isinstance(arr[i], str):
op = arr[i]
num = get_number_of_args(operators[op])
res = operators[op]\(*arr[i-num:i])
arr[i-num] = res
if num == 2:
f=arr.pop(i-num+1)
s=arr.pop(i-num+1)
if num == 1:
f=arr.pop(i-num+1)
i -= num
else:
i += 1
print("The result of", arr_copy, "is:", arr[0])
calc()
I think that the code is so simple that there is no need to spent a lot to explain it but, since the article could be read by everyone and so people not so familiar with coding, I will explain it in detail.
The main idea was to have a modular calculator, it means that if you want to add another function such as cos, sin and so on, you can simply define the function that returns the result, and add it to the operators dictionary. In this dictionary we map the operator that can be found in the rpn expression to the function that calculates its result.
The main function is calc. Let’s explain how it works. First of all it uses an index i to navigate the array arr, which is the only array used for the calculator, no stack or other stuff is implemented. The external cycle is a while that performs everything inside it until the length of the array is different from 1. It will be clear later on why this condition is used.
So, an if condition is used to check if the value at arr[i] is an operator (the operators are treated as strings), if it is, everything inside the if is performed, otherwise, the index i used to navigate the array is simply incremented, to go to the next value in the array.
In case we find an operator, we save it in op variable.
The num variable is important in order to know how many operands the operator has, so to pop the right number of values from the array.
With the next line of code, res = operators[op](*arr[i-num:i]), we save into the variable res the result of the expression that has op as operator and as operands one or two values before the op in the array. The number of operands if 2 for any of the operators in the code except the square root. The * syntax before the arr[i-num:i] is used for unpacking lists, it means that you are telling to the called function that it should take the number of arguments it needs.
The next step is to save the partial result in the current array, at the position of the first operand of the expression, and it is done with arr[i-num] = res.
Then, once we have the partial result, we can pop from the array the useless values, and so the second operand and the operator. The if condition is to check how many operands the called function has, so to pop the right number of times.
Because in the rpn notation we know that we have an initial list of numbers, and then the first operator, the index i used to go through the array is decremented only by the number of operands for the current operator, this is done to avoid unnecessary scrolling of the array.
Once the condition of the while is met, we simply print the result, saved at position 0 in the array.
I was pretty satisfied by my solution, we commented it with the recruiter that did not understand this last aspect of avoiding scrolling the array from the beginning, and when I told him he was even surprised.
A week later, I received an email in which it is specified that I was rejected because I do not have a sufficient technical level required for the R&D team.