Pages

CodeEval Prefix Expressions

The CodeEval problem #7 asks us to write a toy calculator for simple arithmetic expressions written in Polish notation. We expect only addictions, multipications, and divisions. And no inner expressions are allowed, meaning that we can safely expect to have in input firstly all the operators then operands, as integer numbers. We should give an integer answer, even though the internal process should keep correctly track of real numbers generated by divisions.

As sample we are given a unique case, that I converted in a python test:
def test_provided_1(self):
    self.assertEqual(20, solution('* + 2 3 4'))
Since we have only to deal with binary operations, we can use the clever trick of starting from the middle of the input, were we can find the first operand, moving to the left to get the list of operators and to the right for the other operands. This lead naturally to think using zip() a python implementation:
i = len(data) // 2  # 1
result = float(data[i])  # 2
for op, value in zip(reversed(data[0:i]), data[i + 1:]):  # 3
    # ...
1. Getting the central element index in the input data list.
2. Convert the first value to real number, so that floating point arithmetic is applied to the expression.
3. I zip together the left and right part of the input data. First part reversed, so that I start to center and move to the edges fetching elements.

Now, what I should do in the loop. As C programmer my instinct went to a switch on the operators, to detect which operation I have to apply. But Python has no switch, so I had to think to something smarter. I put in a dictionary the mapping between each operator and the actual piece of code I need to run in that context, in form of a lambda function, and then I simply have to lookup in it to have the job done:
mapping = {'+': lambda r, v: r + v, '*': lambda r, v: r * v, '/': lambda r, v: r / v}

# ...

for # ...
    result = mapping[op](result, int(value))
Then, after the for loop, I just have to cast the result to integer and return its value.

On GitHub you can see the unit test and the full python script.

No comments:

Post a Comment