一. 不带括号的中缀表达式转后缀表达式

1.分析

1)先写几个例子(手动模拟转换), 由简单到复杂来观察有什么规律

(1)A+B*C --> ABC*+

(2)A+B*C+D --> ABC*+D+

(3)A+B-C*D/E --> AB+CD*E/-

2)观察可以发现由前缀表达式转后缀表达式二者有很明显的不同:

(1)在1)(1)中运算符的顺序发生了反转,原本是+*变成了*+这让我们直接想到了用栈来保存运算符,然后进行出栈从而得到反转

(2)但是在1)(2)这种运算符的反转不是纯粹的将符号逆置,带有一定的"选择性"

(3)上述例子,运算符的顺序具有选择性的反转,但是操作数的顺序却保持了和中缀表达式一样的相对顺序,我们可以确定操作数的顺 序前缀后后缀的相对性保持一致,我么可以在遍历中缀表达式中只要遍历到操作数就直接将其追加到生成的后缀表达式末尾

(4)算法的难点就在于观察出操作符"选择性"逆置的特性,总结出选择是由什么规则进行的, 这里我也没有通过自己独立观察出来,有待解决,但是书上写的具体的算法是:当栈中操作符优先级大于等于遍历到的操作符优先级将其弹出,直到栈中操作符优先级小于遍历的操作符为止当栈中没有操作符也停止出栈. 对于这段算法的核心思想,我的理解是:栈中保存的操作符优先级高就需要和之前的操作作数进行取出运算,也就是高优先级操作符优先和操作数进行运算,但是优先级相等为什么弹出不是很理解,理解优先级低为什么不弹出那是因为优先级低的弹出了优先级高的就无法相较于优先级低的操作符先与操作数进行运算了,所以肯定不能将优先级低的弹出.

3)由这些例子来分析前缀转后缀的特点,写出所有规律,

在中缀表达式从左到右顺序遍历中缀表达式,遍历过程中:

1)当读到操作数时,直接将其加入后缀表达式末尾

2)当读到操作符时,操作符的右操作数未出现,需要将操作符保存在某处,等到下一个操作符出现后决定是否将其弹出,直到无法继续弹出(两种情况(1)栈为空 (2)可以继续出栈的否命题:当栈中操作符优先级小于遍历到的操作符)

3)一定要注意还有一个情况:当表达式遍历完但是栈中依旧有操作符,则将栈中的操作符全部弹出

#栈的定义===========
class Stack():
    def __init__(self):
        self.body = []
    
    def pop(self):
        return self.body.pop()

    def push(self,elem):
        self.body.append(elem)
    
    def isEmpty(self):
        return self.body == []

    def peek(self):
        return self.body[len(self.body)-1]
#栈的定义===============

def midConvertPostExp(mid_exp):
    stack = Stack()
    post_exp = []
    ope_priority_dic = {'+':1,'-':1,'*':2,'/':2}
    for char in mid_exp:#遍历表达式中的每个字符
        if char not in ope_priority_dic.keys():#遍历的字符不是操作符,题目条件下是运算数
            post_exp.append(char)
        else:#遍历的字符是操作符
            if stack.isEmpty():#当栈为空时,不需比较栈中的元素,直接将当前操作符入栈
                stack.push(char)
            else:
                #当前扫描的表达式为操作符且栈不为空(栈中有其他操作符)⇒与当前操作符的优先级比较,将优先级大于或等于当前操作符的操作符出栈直到栈顶操作符优先级小于当前操作符优先级,或者栈为空时停止出栈
                while  not stack.isEmpty() and ope_priority_dic[char] <= ope_priority_dic[stack.peek()]:#不能使用or连接,这里是继续出栈的条件不是停止出栈的条件,因为当栈不为空且栈顶元素优先级>=表达式运算符才能继续出栈,否则⇔栈为空或者表达式优先级<栈顶优先级则停止,所以应该使用and连接两个条件
                    post_exp.append(stack.pop())
                stack.push(char)

    while not stack.isEmpty():#表达式中元素已经遍历完,但操作符栈依然不为空:
        post_exp.append(stack.pop())
    
    return "".join(post_exp)#join()方法将可迭代对象连接成str

mid_exp = input()
print(midConvertPostExp(mid_exp))

二:带'(' 版本的前缀转后缀

class Stack():
    def __init__(self):
        self.body = []

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

    def push(self, elem):
        self.body.append(elem)

    def isEmpty(self):
        return self.body == []

    def peek(self):
        return self.body[len(self.body) - 1]


# ↑ 栈的定义===============


def midConvertPostExp(mid_exp):
    stack = Stack()
    post_exp = []
    ope_priority_dic = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0}  # 将'()'视为操作符,优先级最低
    for char in mid_exp:  # 遍历表达式中的每个字符
        # 遍历的字符不是操作符,题目条件下是操作数:
        if char not in ope_priority_dic.keys():
            post_exp.append(char)

        else:  # 遍历的字符是操作符
            # 入栈逻辑:栈空或者优先级大于等于则入栈
            if stack.isEmpty() or ope_priority_dic[char] >= ope_priority_dic[stack.peek()]:
                stack.push(char)

            # 出栈情况1: --)匹配(	:
            elif char == ')':
                top_char = stack.pop()
				while top_char != '('
					post_exp.append(top_char)
					top_char = stack.pop()
            # 出栈情况2: 当前字符串操作符优先级小于栈顶
            elif ope_priority_dic[char] < ope_priority_dic[stack.peek()]:
                while ope_priority_dic[char] < ope_priority_dic[stack.peek()] and not stack.isEmpty():
                    post_exp.append(stack.pop())


    # 当表达式中元素已经遍历完,但操作符栈依然不为空的情况(出栈去报个价2):
    while not stack.isEmpty():
        post_exp.append(stack.pop())
    return "".join(post_exp)

# 主调函数:
mid_exp = input()
print(midConvertPostExp(mid_exp))

下面是另一个版本的处理逻辑,将入栈的情况:遍历到操作符的前提下,栈空或遍历到的中缀表达式操作符优先级>=栈中操作符的优先级,出栈的情况2)当前缀表达式遍历到的操作符优先级小于栈顶 用一个逻辑表达出来.

def infixToPostfix(mid_exp):
    op_pri_dic = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0,')':0}
    op_stack = Stack()
    post_fix_list = []

    for char in mid_exp:
        #1)char = 字母⇒加入列表
        if char not in op_pri_dic:
            post_fix_list.append(char)
        #2) char = ( ⇒ 入栈-1
        elif char == '(':
            op_stack.push(char)
        #3)char =  ) ⇒ 出栈直到匹配(
        elif char == ')':
              #先出栈,并且获取字符,是'('就跳过,不是'('就进入循环来继续出栈:
            topToken = op_stack.pop()
            while topToken != '(':
                post_fix_list.append(topToken)
                topToken = op_stack.pop()

        #4) char == 其余情况 ⇔ char == +-*/
		#将入栈的情况:遍历到操作符的前提下,栈空或遍历到的中缀表达式操作符优先级>=栈中操作符的优先级,出栈的情况2)当前缀表达式遍历到的操作符优先级小于栈顶 用一个逻辑表达出来.
        else:
            #char == +-*/的前提下, 栈不为空 且 栈顶元素优先级大于等于当前运算符优先级时:
            #一直出栈运算符到列表,直到条件不满足⇔栈为空或栈顶元素优先级小于当前运算符,最后将该运算符入栈
            while (not op_stack.isEmpty()) and (op_pri_dic[op_stack.peek()]>=op_pri_dic[char]):
                post_fix_list.append(op_stack.pop())
            op_stack.push(char)

    while not op_stack.isEmpty():
        post_fix_list.append(op_stack.pop())


    return "".join(post_fix_list)

mid_exp = input()
print(infixToPostfix(mid_exp))