用Python如何评估紧凑形式的前缀表达式？

Question

用Python如何评估紧凑形式的前缀表达式？

4

我目前正在一个名为Singpath的网站上解决Python问题集。问题如下：

前缀表达式求值创建一个函数，以前缀表示法计算算术表达式，不带空格或语法错误。该表达式作为字符串给出，表达式中的所有数字都是0~9的整数，运算符是+(加法)、-(减法)、*(乘法)、/(除法)、%(取模)，其操作与Python中的操作完全相同。前缀表示法，也称为波兰表示法，是一种用于逻辑、算术和代数的表示法。它将运算符放在它们的操作数左边。如果运算符的arity是固定的，则结果是一个无括号或其他括号的语法，仍然可以被解析而没有歧义。

这似乎很简单，但输入的字符串没有空格，如何分离数据？如何使用数据的结果来解决给定的方程？请注意，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:

- Winkleson

6个回答

3

我认为这里最重要的一点是“表达式中所有数字都是0~9的整数”。所有数字都是单个数字。你不需要空格来确定一个数字在哪里结束，下一个数字从哪里开始。你可以通过它们的字符串索引直接访问这些数字，就像lckknght所说的那样。

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

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

- brightbyte

当我在打答案时，我考虑过使用ASCII值，但最终决定不尝试，因为我想以全新的视角看待这个问题:P 谢谢你的建议！ - Winkleson

2

你的 "一个函数" 的限制并不像你想象的那样糟糕。Python 允许在函数内定义函数。最终，函数定义仅仅是将函数分配给一个（通常是新的）变量。在这种情况下，我认为你会想使用递归。虽然这也可以在没有额外函数的情况下完成，但你可能会发现定义一个额外的递归函数更容易。这对你的限制来说并不是问题：

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

如果你想使用递归方法，这应该足够提示了。

- Bas Wijnen

和Sean一样，我不太擅长递归，所以我应该查找一个教程/分解它的方法。谢谢你的提示！如果我没有得到详细的答案，那么我会在互联网上搜索递归，这将引导我朝着正确的方向前进。干杯！ - Winkleson

我从未知道你可以在一个函数中创建另一个函数，我以为那是一个大忌讳。 :P 谢谢你的提示，将来应该会派上用场！编辑：当我打这个回答时，我的前一个评论还没有出现……我更喜欢这个......再次感谢！ - Winkleson

2

嗯，一行代码就搞定了？在Python3中，reduce函数被隐藏在functools模块中。有点像Lisp语言 :)

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]

- alex_jordan

3

谢谢你提供这么复杂的代码...唯一的问题是...我是一个编程初学者...我还不是很擅长Python :P 所以...如果你想真正帮助我，可以随意扩展它。XD - Winkleson

0

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

def eval_prefix(data):
    # setup state machine
    for symbol_ in data:
        # update state machine

- Sean Vieira

谢谢Sean，但我已经掌握了这么多......问题在于从字符串到列表的转换和适当的递归......我对这些东西很新:P 谢谢XD - Winkleson

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进行调用，则会更容易）。

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

- Blckknght

啊...愚蠢的电脑刚才把我的评论给偷了 :P 所以，总结一下：非常感谢你提供的递归定义（和建议），易于阅读的字符串 -> 列表转换，以及你花费的时间。再次感谢！ - Winkleson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Gaines Jr. · Accepted Answer

好的，虽然不像alex jordan的lambda/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)