4

我目前正在一个名为 singpath 的网站上研究 python 问题集。问题是：

前缀求值 创建一个函数，以前缀符号的形式对算术表达式求值，没有空格或语法错误。表达式以字符串形式给出，表达式中的所有数字均为整数 0~9，运算符为 +（加）、-（减）、*（乘）、/（除）、%（取模），其中操作与 Python 中的操作相同。前缀表示法，也称为波兰表示法，是逻辑、算术和代数的一种表示法。它将运算符放在操作数的左侧。如果运算符的数量是固定的，则结果是缺少括号或其他括号的语法，仍然可以毫无歧义地解析。

这看起来很简单，但是字符串被压缩，输入中没有空格来拼接数据。如何在不导入模块的情况下将数据与字符串分开？此外，我如何使用数据结果来求解给定的方程？另请注意，Singpath 解决方案必须在一个不能使用标准 python 库中找不到的方法的函数中。这还包括在解决方案中声明的函数：S

例子：

>>> eval_prefix("+34")
7
>>> eval_prefix("*−567")
-7
>>> eval_prefix("-*33+2+11")
5
>>> eval_prefix("-+5*+1243")
14
>>> eval_prefix("*+35-72")
40
>>> eval_prefix("%3/52")
1

请参阅我的观点，没有空格 D：

4

6 回答 6

3

好的，不像 alex jordan 的 lamba/reduce 解决方案那样时髦，但它不会因垃圾输入而窒息。这是一种递归下降解析器遇到冒泡排序的厌恶（我认为当它找到一个可解决的部分时，它可能比仅仅跳回开始更有效率。;）

import operator
def eval_prefix(expr):
    d = {'+': operator.add,
         '-': operator.sub,
         '*': operator.mul,
         '/': operator.div, # for 3.x change this to operator.truediv
         '%': operator.mod}
    for n in range(10):
        d[str(n)] = n
    e = list(d.get(e, None) for e in expr)
    i = 0
    while i + 3 <= len(e):
        o, l, r = e[i:i+3]
        if type(o) == type(operator.add) and type(l) == type(r) == type(0):
            e[i:i+3] = [o(l, r)]
            i = 0
        else:
            i += 1
    if len(e) != 1:
        print 'Error in expression:', expr
        return 0
    else:
        return e[0]

def test(s, v):
    r = eval_prefix(s)
    print s, '==', v, r, r == v

test("+34", 7)
test("*-567", -7)
test("-*33+2+11", 5)
test("-+5*+1243", 14)
test("*+35-72", 40)
test("%3/52", 1)
test("****", 0)
test("-5bob", 10)
于 2012-11-14T23:14:45.833 回答
3

我认为这里的关键是“表达式中的所有数字都是整数 0~9”。所有数字都是个位数。您不需要空格来找出一个数字的结束位置和下一个数字的开始位置。正如 lckknght 所说，您可以通过它们的字符串索引直接访问这些数字。

要将字符串中的字符转换为整数进行计算，请使用 ord(ch) - 48（因为“0”的 ASCII 码为 48）。因此，要获取存储在输入位置 5 的数字，请使用 ord(input[5]) - 48。

要评估嵌套表达式，您可以递归调用函数。这里的关键假设是一个操作符总是恰好有两个操作符。

于 2012-11-14T22:56:13.410 回答
2

您的“单一功能”限制并不像您想象的那么糟糕。Python 允许在函数内部定义函数。最后，函数定义只不过是将函数分配给（通常是新的）变量。在这种情况下，我想你会想要使用递归。虽然这也可以在没有额外函数的情况下完成，但您可能会发现为它定义额外的递归函数更容易。这对您的限制没有问题：

def eval_prefix (data):
    def handle_operator (operator, rest):
        # You fill this in.
    # and this, too.

这应该是足够的提示（如果你想使用递归方法）。

于 2012-11-14T21:25:53.187 回答
2

那么，单线适合吗？Python3 中的 Reduce 隐藏在 functools 中有点 lispy :)

eval_prefix = lambda inp:\
            reduce(lambda stack, symbol:\
            (
              (stack+[symbol]) if symbol.isdigit() \
             else \
              (
                stack[:-2]+\
                [str(
                      eval(
                           stack[-1]+symbol+stack[-2]
                          )
                    )
                ]
              )
            ), inp[::-1], [])[0]
于 2012-11-14T21:50:33.463 回答
0

您最有可能寻找的提示是“字符串是可迭代的”：

def eval_prefix(data):
    # setup state machine
    for symbol_ in data:
        # update state machine
于 2012-11-14T21:20:44.060 回答
0

分离字符串的元素很容易。所有元素都是单个字符长，因此您可以直接迭代（或索引）字符串以获取每个元素。或者，如果您希望能够操作这些值，您可以将字符串传递给list构造函数。

以下是一些如何工作的示例：

string = "*-567"

# iterating over each character, one at a time:
for character in string:
    print(character) # prints one character from the string per line

# accessing a specific character by index:
third_char = string[2] # note indexing is zero-based, so 3rd char is at index 2

# transform string to list
list_of_characters = list(string) # will be ["*", "-", "5", "6", "7"]

至于如何解方程，我认为有两种方法。

一种是使您的函数递归，以便每个调用评估单个操作或文字值。这有点棘手，因为您只应该使用一个函数（如果您可以使用与主非递归函数不同的 API 调用递归辅助函数，那会容易得多）。

另一种方法是建立一堆值和操作，等待评估，同时对输入字符串进行一次迭代。考虑到单一功能的限制，这可能更容易。

于 2012-11-14T21:29:15.407 回答