转换前缀表示法中给出的表达式,标识公共子表达式和依赖项

Question

我在ANSI文本文件中的前缀表示法中给出了一堆表达式.我想生成另一个ANSI文本文件,其中包含对这些表达式的逐步评估.例如:

- + ^ x 2 ^ y 2 1

应该变成

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

我还必须识别常见的子表达式.举个例子

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

我必须生成一个输出,说x出现在表达式1,2和3(通过z)中.

我必须识别依赖:expression_1仅依赖于x,expression_2依赖于x和y等.

原始问题比上面的例子更困难,我无法控制输入格式,它以前缀表示法比上面的方式复杂得多.

我已经在C++中有一个工作实现,但是在C++中做这些事情是很痛苦的.

哪种编程语言最适合这些类型的问题？

你能推荐我可以开始的教程/网站/书吗？

我应该寻找哪些关键字？

更新:基于答案,上面的例子有点不幸,我在输入中有一元,二元和n元运算符.(如果你想知道,exp是一个一元运算符,sum在一个范围内是一个n-ary运算符.)

Answer 1

为了让您了解Python中的结果,下面是一些示例代码:

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"

输出与示例输出相同.

除了这个例子,我认为你列出的任何高级语言几乎都适合这项任务.

Answer 2

该问题由两个子问题组成：解析和符号操作。在我看来，答案可以归结为两种可能的解决方案。

一是从头开始实现一切：“如果您想保留处理棘手情况的最大灵活性，我确实建议您创建完整的表达式树。” - 由雷克斯提出。正如 Sven 指出的那样：“您列出的任何高级语言几乎同样适合该任务”，但是“Python（或您列出的任何高级语言）不会消除问题的复杂性。 ”
我收到了非常好的 Scala 解决方案（非常感谢 Rex 和 Daniel），这是一个很好的 Python 小示例（来自 Sven）。然而，我仍然对 Lisp、Haskell 或 Erlang 解决方案感兴趣。

另一种解决方案是使用一些现有的库/软件来完成任务，并具有所有隐含的优点和缺点。候选者是 Maxima (Common Lisp)、SymPy (Python，由 payne 提出) 和 GiNaC (C++)。