Transforming expression given in prefix notation, identifying common subexpressions and dependencies

Question

I am given a bunch of expressions in prefix notation in an ANSI text file. I would like to produce another ANSI text file containing the step-by-step evaluation of these expressions. For example:

- + ^ x 2 ^ y 2 1

should be turned into

t1 = x^2
t2 = y^2
t3 = t1 + t2
t4 = t3 - 1
t4 is the result

I also have to identify common subexpressions. For example given

expression_1: z = ^ x 2
expression_2: - + z ^ y 2 1
expression_3: - z y

I have to generate an output saying that x appears in expressions 1, 2 and 3 (through z).

I have to identify dependecies: expression_1 depends only on x, expression_2 depends on x and y, etc.

The original problem is more difficult than the examples above and I have no control over the input format, it is in prefix notation in a much more complicated way than the above ones.

I already have a working implementation in C++ however it is a lot of pain doing such things in C++.

What programming language is best suited for these type problems?

Could you recommend a tutorial / website / book where I could start?

What keywords should I look for?

UPDATE: Based on the answers, the above examples are somewhat unfortunate, I have unary, binary and n-ary operators in the input. (If you are wondering, exp is an unary operator, sum over a range is an n-ary operator.)

Answer 1

To give you an idea how this would look like in Python, here is some example code:

operators = "+-*/^"

def parse(it, count=1):
    token = next(it)
    if token in operators:
        op1, count = parse(it, count)
        op2, count = parse(it, count)
        tmp = "t%s" % count
        print tmp, "=", op1, token, op2
        return tmp, count + 1
    return token, count

s = "- + ^ x 2 ^ y 2 1"
a = s.split()
res, dummy = parse(iter(a))
print res, "is the result"

The output is the same as your example output.

This example aside, I think any of the high-level languages you listed are almost equally suited for the task.

Answer 2

The sympy python package does symbolic algebra, including common subexpression elimination and generating evaluation steps for a set of expressions.

See: http://docs.sympy.org/dev/modules/rewriting.html (Look at the cse method at the bottom of the page).