Python 将中缀转换为前缀表示法的程序

Question

我一直收到 IndexError: list index out of range, return self.data[-1] # 列表中的最后一个元素；我想我知道是什么原因造成的，但我不知道如何解决它

这是堆栈 Class 我用过的：

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)*(c-d)

预期输出：

*+ab-cd

Answer 1

你有 A = A + '('。那增加了错误的一端。只需执行 A = '('+A+')' 并跳过额外的推送。
您给 ')' 的优先级与 '^' 相同。在 operatorpriority 中，您的 else: 应该是 elif x =='^':.
在你的 elif A[i] == "(" 子句中，你弹出直到 '('。那是错误的括号类型。并且你不会在堆栈为空之前跳出循环。你需要在什么时候跳出你得到一个')'。
您的示例显示 (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)'))

Python 将中缀转换为前缀表示法的程序

Python program to convert infix to prefix notation

python

stack

polish-notation