python - python中的前缀符号解析

Question

马上开始 - 不，这不是家庭作业。

我想用 python 编写一个前缀符号解析器(目前用于求和)...例如

如果给定:+ 2 2 它将返回:4

想法？

Answer 1

前缀表示法可以很容易地递归求值。您基本上会看到第一个标记，如果它是一个“+”，您将评估后面的子表达式以获取要添加的值并将它们相加。如果它是一个数字，您只需返回该数字。

以下代码假定输入格式正确并且是一个有效的表达式。

#! /usr/bin/env python
from collections import deque
def parse(tokens):
    token=tokens.popleft()
    if token=='+':
            return parse(tokens)+parse(tokens)
    elif token=='-':
            return parse(tokens)-parse(tokens)
    elif token=='*':
            return parse(tokens)*parse(tokens)
    elif token=='/':
            return parse(tokens)/parse(tokens)
    else:
            # must be just a number
            return int(token)


if __name__=='__main__':
        expression="+ 2 2"
        print parse(deque(expression.split()))