python中的中缀到后缀算法

idv4meu8  于 2023-03-24  发布在  Python
关注(0)|答案(3)|浏览(101)

在我的数据结构课上,我必须使用Python 3创建一个基本的图形计算器。要求是我们必须使用一个基本的Stack类。用户以“中缀”的形式输入方程,然后我应该将其转换为“后缀”以进行计算和绘图。我在使用中缀到后缀算法时遇到了麻烦。我已经看到其他算法可以工作,但我的教授希望以某种方式完成。以下是我目前掌握的情况:

def inFixToPostFix():
inFix = '3*(x+1)-2/2'
postFix = ''
s = Stack()
for c in inFix:
    # if elif chain for anything that c can be
    if c in "0123456789x":
        postFix += c
    elif c in "+-":
        if s.isEmpty():
            s.push(c)
        elif s.top() =='(':
            s.push(c)
    elif c in "*/":
        if s.isEmpty():
            s.push(c)
        elif s.top() in "+-(":
            s.push(c)
    elif c == "(":
        s.push(c)
    elif c == ")":
        while s.top() is not '(':
            postFix += s.pop()
        s.pop()
    else:
        print("Error")
print(postFix)
return postFix

当我打印这个我得到'3x 1 +22'当预期的结果是'3x 1 +*22/-'任何帮助将不胜感激。谢谢。

fjnneemd

fjnneemd1#

你应该在退出循环后弹出堆栈上剩余的操作数。该算法非常简单,但如果你需要信息,这里解释:
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
以下是我的解决方案,如果你需要的话:)

def toPostfix(infix):
    stack = []
    postfix = ''

    for c in infix:
        if isOperand(c):
            postfix += c
        else:
            if isLeftParenthesis(c):
                stack.append(c)
            elif isRightParenthesis(c):
                operator = stack.pop()
                while not isLeftParenthesis(operator):
                    postfix += operator
                    operator = stack.pop()              
            else:
                while (not isEmpty(stack)) and hasLessOrEqualPriority(c,peek(stack)):
                    postfix += stack.pop()
                stack.append(c)

    while (not isEmpty(stack)):
        postfix += stack.pop()
    return postfix
h43kikqp

h43kikqp2#

class stack:
        def __init__(self):
            self.item = []
        
        def push(self,it):
            self.item.append(it)
        def peek(self):
            if self.isempty() == True:
                return 0
            return self.item[-1]
        
        def pop(self):
            if self.isempty() == True:
                return 0
            return(self.item.pop())
        
        def length(self):
            return (len(self.item))
        
        
        def isempty(self):
            if self.item == []:
                return True
            else:
                return False
        
        def display(self):
            if self.isempty()== True:
                return
            temps = stack()
            while(self.isempty() != True):
                x = self.peek()
                print("~",x)
                temps.push(x)
                self.pop()
            while(temps.isempty() != True):
                x = temps.peek()
                self.push(x)
                temps.pop()
    
    
        def isOperand(self, ch): 
            return ch.isalpha()
        def notGreater(self, i):
            precedence = {'+':1, '-':1, '*':2, '/':2, '%':2, '^':3}
            if self.peek() == '(':
                return False
            a = precedence[i]
            b = precedence[self.peek()] 
            if a  <= b:
                return True
            else:
                return False
                
    
        
        def infixToPostfix(self, exp):
            output = ""
            
            for i in exp:
                
                if self.isOperand(i) == True: # check if operand add to output
                    print(i,"~ Operand push to stack")
                    output = output + i
    
                # If the character is an '(', push it to stack 
                elif i  == '(':
                    self.push(i)
                    print(i," ~ Found ( push into stack")
    
                elif i == ')':  # if ')' pop till '('
                    while( self.isempty() != True and self.peek() != '('):
                        n = self.pop() 
                        output = output + n
                        print(n, "~ Operator popped from stack")
                    if (self.isempty() != True and self.peek() != '('):
                        print("_________")
                        return -1
                    else:
                        x = self.pop()
                        print(x, "Popping and deleting (")
                else: 
                    while(self.isempty() != True and self.notGreater(i)):
                        c = self.pop()
                        output = output + c
                        print(c,"Operator popped after checking precedence from stack")
                    self.push(i)
                    print(i,"Operator pushed to stack")
    
            # pop all the operator from the stack 
            while self.isempty() != True:
                xx = self.pop()
                output = output + xx
                print(xx,"~ pop at last")
            print(output)
            self.display()
        st = stack()
        st.infixToPostfix("a+(b*c)")

这里有一个完整的算法,一步一步的工作细节。
输出:

a ~ Operand push to stack
+ Operator pushed to stack
(  ~ Found ( push into stack
b ~ Operand push to stack
* Operator pushed to stack
c ~ Operand push to stack
* ~ Operator popped from stack
( Popping and deleting (
+ ~ pop at last
abc*+
2uluyalo

2uluyalo3#

在算法中需要大量的修改才能使其正确。
1.对于后缀字符串使用这种类型的字符串表示,稍后在评估它们时,您可能最终会得到与2+34和23+4相同的表示,即234+
1.如果遇到的操作数的优先级低于操作数堆栈顶部的操作数,则从操作数堆栈弹出并将其推送到后缀堆栈(您还没有这样做)
1.在完成给定中缀串的遍历之后,操作数栈中的剩余操作数应当从操作数栈中弹出并被压入后缀栈。
这是数据结构课程的初始任务之一,因为它真正承认你使用堆栈。因此,我不会分享我的代码,因为我认为你可以自己实现。仍然有困难,分享障碍,我会引导你一条通往目的地的道路。

相关问题