Python堆栈越界错误

Question

我在堆栈的push方法上得到一个索引越界错误。

我试图在python中实现一个后缀风格的逻辑计算器。其中，例如0!1&1!0=!1/|将评估为1或true。

我使用堆栈和与列表"push"one_answers"pop"相关的常见方法来实现这一点，但我不允许使用在这种实现中可能很好的典型的追加或删除方法。相反，我必须将列表初始化为一个标准大小，该大小等于我将对其执行评估的表达式的长度

我通过引用一个名为top的全局整数来使用我的方法evaluate实现这一点，该全局整数指向堆栈的顶部，并根据我调用push还是pop在内部递增或递减。

我的push方法如下

def push(stack, element):
    global tos
    tos += 1
    stack[tos] = element

我的pop方法如下

def pop(stack):
    #stack = None
    global tos
    tos -= 1

本质上，我使用读取字符串的每个单独元素

for i in expression

然后我说，if i ==（一些表达式）：执行预制方法。

下面是我在这个循环中发现的代码中的几个例子，它迭代了表达式

if op == "1":
    push(theStack, True)
elif op == "0":
    push(theStack, False)
elif op == "!":
    pop(None)
    push(theStack, Not(theStack[tos]))
elif op == "&":
    pop(None)
    pop(None)
    push(theStack, And(theStack[tos], theStack[tos + 1]))

我测试了pop，它似乎做了该做的事。我认为错误是我的push。

我将tos初始化为-1，这也是在中发现循环的方法顶部的一个快速峰值

def LogicalEval (expression):
    global tos
    theStack = [len(expression)]
    def Not(expr):
        if expr == True:
            return False
        else:
            return True
    def And (expr1, expr2):
        if expr1 == True and expr2 == True:
            return True
        else:
            return False

我不会在LogicalEval之外的任何点启动堆栈，事实上，我仅限于助手方法之外的三个主要方法（push、pop、LogicalEval），如LogicalEval 中的And和Not

您创建了一个包含一个元素的堆栈：

theStack = [len(expression)]

len()返回一个整数，因此您创建了以下列表，给定一个5字符的表达式：

theStack = [5]

所以你会很快用完空间。

创建这样的列表：

theStack = [None] * len(expression)

一个序列上的乘法重复该序列。[None]是一个包含一个元素的列表（None的哨值），将其乘以表达式的长度将创建一个包含那么多元素的列表。

接下来，对于!和&:，您对堆栈上操作数的处理是不正确的

elif op == "!":
    pop(None)
    push(theStack, Not(theStack[tos]))
elif op == "&":
    pop(None)
    pop(None)
    push(theStack, And(theStack[tos], theStack[tos + 1]))

您希望首先检索堆栈值，然后检索pop()；或者调整tos偏移量以考虑它们已经减少，或者将pop()函数更改为返回弹出值。

目前，当您运行!（booleanNOT）时，您将从tos == 0移动到tos == -1，然后将Not(theStack[-1])推回到堆栈上。这不是您想要做的，因为theStack[-1]是堆栈中的最后一个元素，而不是当前活动堆栈的一部分。

然后在具有tos == 2的堆栈上执行&（布尔值AND），并弹出两次。现在您再次访问0，并尝试寻址theStack[0]和theStack[1]。在这里，从堆栈的偏移是完全不正确的；您刚刚从tos中删除了两个，然后添加0和1，寻址旧堆栈顶部下方的两个值。

我个人会选择一个pop()函数，它返回堆栈的顶部并调整tos指针：

def pop(stack):
    global tos
    tos -= 1
    return stack[tos + 1]  # value at old position

然后使用它从堆栈中获取操作数：

elif op == "!":
    push(theStack, Not(pop(theStack)))
elif op == "&":
    push(theStack, And(pop(theStack), pop(theStack)))

theStack = [len(expression)]不创建长度为len(expression)的列表，而是创建长度为1的列表，其中包含theStack[0]中的值len(expression)。

要创建给定长度的列表，可以执行

theStack = [0] * len(expression)]

这将把theStack的len(expression)元素初始化为零。