0

我不断收到 IndexError: list index out of range, return self.data[-1] # the last element in the list; 我想我知道是什么原因造成的，但我不知道如何解决它

这是我使用的堆栈类：

class Stack: 
    # LIFO Stack implementation using a Python list as underlying storage.
    def __init__(self): 
        self.data =[]   

    def __len__(self):  
        return len(self.data)

    def is_empty(self): 
        return len(self.data)==0

    def push(self, e):  
        self.data.append(e) 

    def top(self):       
        return self.data[-1] 

    def pop(self):      
        return self.data.pop()

以及我制作的相应代码：

def operatorpriority(x):
    if x == "+" or x == "-":
        return 1
    elif x == "*" or x == "/":
        return 2
    else:
        return 3
    return 0

def polishnotation(A):
    # Converts Infix to Prefix Notation
    stack = Stack()
    stack.push(')')
    A = A + '('
    output = ""
    for i in range(len(A)-1, -1, -1):
        print(i)
        if A[i].isnumeric() == True:
            output+=A[i]
        elif A[i] == ")":
            stack.push(A[i])
        elif A[i] == "-" or A[i] == "+" or A[i] == "*" or A[i] == "/" or A[i] == "^":
            if A[i] == "^":
                while operatorpriority(A[i]) <= operatorpriority(stack.top()):
                    output+=stack.pop()
            else:
                while operatorpriority(A[i]) < operatorpriority(stack.top()):
                    output+=stack.pop()
            stack.push(A[i])
        elif A[i] == "(":
            while stack.is_empty()== False:
                if stack.top() != "(":
                    output+=stack.pop()
                stack.pop()
    while stack.is_empty()== False:
        output+=stack.pop()
    print(output)

InfixInput = input("Input infix notation: ")

polishnotation(InfixInput)

样本输入：

(a+b)*(cd)

预期输出：

*+ab-cd

4

1 回答 1

0
  1. 你有A = A + '('. 这增加了错误的结束。只需做A = '('+A+')'并跳过额外的推动。
  2. 您给予 ')' 与 '^' 相同的优先级。在operatorpriority，你else:应该是elif x =='^':。
  3. 在您的elif A[i] == "("子句中，您一直弹出直到'（'。这是错误类型的括号。并且在堆栈为空之前，您不会跳出该循环。当您到达“）”时，您需要中断。
  4. 您的示例显示(a+b)*(c+d)，但您的代码只允许数字。我没有改变这一点。

这有效：

class Stack: 
    # LIFO Stack implementation using a Python list as underlying storage.
    def __init__(self): 
        self.data =[]   

    def __len__(self):  
        return len(self.data)

    def is_empty(self): 
        return len(self.data)==0

    def push(self, e):  
        self.data.append(e) 

    def top(self):       
        return self.data[-1] 

    def pop(self):      
        return self.data.pop()

def operatorpriority(x):
    if x in "+-":
        return 1
    elif x in "*/":
        return 2
    elif x in "^":
        return 3
    return 0

def polishnotation(A):
    # Converts Infix to Prefix Notation
    stack = Stack()
    A = '(' + A + ')'
    output = ""
    for c in A[::-1]:
        print(c)
        if c.isnumeric():
            output+=c
        elif c == ")":
            stack.push(c)
        elif c in "+-*/^":
            if c == "^":
                while operatorpriority(c) <= operatorpriority(stack.top()):
                    output+=stack.pop()
            else:
                while operatorpriority(c) < operatorpriority(stack.top()):
                    output+=stack.pop()
            stack.push(c)
        elif c == "(":
            while not stack.is_empty():
                c1 = stack.pop()
                if c1 == ')':
                    break
                output+=c1
    while not stack.is_empty():
        output+=stack.pop()
    return output

print(polishnotation('(3+4)*(5+6)'))
于 2022-02-11T07:36:43.960 回答