Internet Problem Solving Contest

IPSC 2009

Solution to Problem A – Arithmetics for dummies

There are two ways to solve this problem.

The more annoying way is to write your own program that parses the input and does the math.

The advantage of this approach is that the missing operator preference makes it possible to read the numbers and operations one at a time and execute them. This gets even easier in the case of interpreted languages that have some way of evaluating expressions in strings.

Still, probably a better way is to pass the expressions into some existing tool / calculator (such as bc in linux).

For the hard test case, we may need to force the tool to evaluate the expressions in correct order. One possibility is to add parentheses to the expression in such a way that the operator preference would not matter. This means adding a closing parenthesis before each operator and an equal number of opening parenthesis to the beginning of the line. This can be achieved directly with a sed script (though it may be a bit complicated) or by the combination of sed and grep.

Another solution is to swap the numbers and operators and use a calculator that uses the reverse polish notation such as dc. This can be easily accomplished by a simple regexp: s,([-+*/]) *([0-9]+),\2 \1,g. We also need to change the equal sign into a p command that prints the result after each line.