T24591: 中序表达式转后序表达式

stack, ast, http://cs101.openjudge.cn/practice/24591/

中序表达式是运算符放在两个数中间的表达式。乘、除运算优先级高于加减。可以用"()"来提升优先级 --- 就是小学生写的四则算术运算表达式。中序表达式可用如下方式递归定义：

1）一个数是一个中序表达式。该表达式的值就是数的值。

若a是中序表达式，则"(a)"也是中序表达式(引号不算)，值为a的值。
若a,b是中序表达式，c是运算符，则"acb"是中序表达式。"acb"的值是对a和b做c运算的结果，且a是左操作数，b是右操作数。

输入一个中序表达式，要求转换成一个后序表达式输出。

输入

第一行是整数n(n<100)。接下来n行，每行一个中序表达式，数和运算符之间没有空格，长度不超过700。

输出

对每个中序表达式，输出转成后序表达式后的结果。后序表达式的数之间、数和运算符之间用一个空格分开。

样例输入

3
7+8.3 
3+4.5*(7+2)
(3)*((3+4)*(2+3.5)/(4+5))

样例输出

7 8.3 +
3 4.5 7 2 + * +
3 3 4 + 2 3.5 + * 4 5 + / *

来源

Guo wei

接收浮点数，是number buffer技巧。

python

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2}
    stack = []
    postfix = []
    number = ''

    for char in expression:
        if char.isnumeric() or char == '.':
            number += char
        else:
            if number:
                num = float(number)
                postfix.append(int(num) if num.is_integer() else num)
                number = ''
            if char in '+-*/':
                while stack and stack[-1] in '+-*/' and precedence[char] <= precedence[stack[-1]]:
                    postfix.append(stack.pop())
                stack.append(char)
            elif char == '(':
                stack.append(char)
            elif char == ')':
                while stack and stack[-1] != '(':
                    postfix.append(stack.pop())
                stack.pop()

    if number:
        num = float(number)
        postfix.append(int(num) if num.is_integer() else num)

    while stack:
        postfix.append(stack.pop())

    return ' '.join(str(x) for x in postfix)

n = int(input())
for _ in range(n):
    expression = input()
    print(infix_to_postfix(expression))

接收数据，还可以用re处理。

python

# 24591:中序表达式转后序表达式
# http://cs101.openjudge.cn/practice/24591/

def inp(s):
    #s=input().strip()
    import re
    s=re.split(r'([\(\)\+\-\*\/])',s)
    s=[item for item in s if item.strip()]
    return s

exp = "(3)*((3+4)*(2+3.5)/(4+5)) "
print(inp(exp))

python

def tokenize(expression):
    import re
    tokens = re.findall(r'\d+.\d+|\d+|\D', expression)
    tokens = [token.strip() for token in tokens if token.strip()]
    return tokens

exp = "(3)*((3+4)*(2+3.5)/(4+5)) "
print(tokenize(exp))
# ['(', '3', ')', '*', '(', '(', '3', '+', '4', ')', '*', '(', '2', '+', '3.5', ')', '/', '(', '4', '+', '5', ')', ')']

卢卓然-23-生命科学学院，思路：

首先我们来考虑一个括号内的转化。对于一个括号内的表达式，可以写为这种格式：乘除加减乘除加减乘除。其中，乘除可以包括连乘连除或先乘后除。注意：中序和后序的数字相对位置是不变的。

对于连续同级运算的转换，例如1+2-3转化为12+3-，其规律为：从左向右遍历表达式，若遇到运算符，则证明前一个运算符已经算完了，所以在后序中添加前一个运算符。例如遍历到减号，则说明1+2的运算已经结束，按照同级运算从左到右的原则，应该在后序表达式里写12+。然后将减号储存起来。遍历完3后，储存器内剩了一个减号，把这个减号加到表达式最后。

接着考虑如加粗字体所示的表达式形式（没有括号），倘若遍历到一个加号或减号，就说明其前面的乘除表达式已经计算完毕了，根据上一段的内容，应该将储存器内剩余的一个乘除号添加到末尾。而后，倘若储存器中还剩余加减运算（当前加减号之前的加减号），那么说明这个加减运算已经运算完毕（因为这个加减运算的两个因子都计算完了），所以要把这个加减号写到表达式的末尾。最后，将当前加减号加入储存器。就可以一直运行下去。

如果带括号，那么带括号的部分要做到单独运算，括号内部的规则与上面是一样的。因此，可以界定一个“边界”，也就是左括号的位置。如果遇到了右括号，就需要把括号内剩余的加减乘除完成。相当于在每一个括号内运行了上面的代码。具体实现如下，函数trans_input()是将输入数据改成易于操作的列表形式。

代码

python

'''带括号的部分独立运算
（表达式）->后序表达式，再与其他组合在一起
遇到(入栈，遇到操作符同上操作，遇到）弹出（之后所有操作符，相当于独立处理了这部分。
'''
def trans_input(string):
    '''处理输入数据,返回所需列表l'''
    operators={'+','-','*','/','(',')'}
    l=[]
    i=0
    string=string.strip()
    length=len(string)
    flag=False
    while i<length:
        letter=string[i]
        if letter!='.' and letter not in operators:
            if not flag:
                flag=True
                l.append(letter)
                i+=1
            else:
                l[-1]=l[-1]+letter
                i+=1
        elif letter in operators:
            flag=False
            l.append(letter)
            i+=1            
        elif letter=='.':
            temp='.'
            j=i+1
            while j<length and string[j].isdigit()==True:
                temp=temp+string[j]
                j+=1
            i=j
            l[-1]=l[-1]+temp
    return l
case=int(input())
output=[]
for _ in range(case):
    infix_notation=input()
    l=trans_input(infix_notation)
    operators={'+','-','*','/','(',')'}
    result_stack=[]
    operator_stack=[]
    n=len(l)
    for i in range(n):
        letter=l[i]
        if letter not in operators:
            result_stack.append(letter)
        else:
            if letter=='(':
                operator_stack.append(letter)
            elif letter=="*" or letter=='/':
                while operator_stack and operator_stack[-1]!='(' and (operator_stack[-1]=='*' or operator_stack[-1]=='/'):
                    p=operator_stack.pop(-1)
                    result_stack.append(p)
                operator_stack.append(letter)
            elif letter==')':#将括号内剩余的加减写出来
                while operator_stack[-1]!='(':
                    p=operator_stack.pop(-1)
                    result_stack.append(p)
                operator_stack.pop(-1)#删除'('
            else:#letter是加减的情况
                while operator_stack and operator_stack[-1]!='(':
                    p=operator_stack.pop(-1)
                    result_stack.append(p)
                operator_stack.append(letter)
    while operator_stack:#整体剩余的加减写出来
        p=operator_stack.pop(-1)
        result_stack.append(p)
    output.append(' '.join(result_stack))
for o in output:
    print(o)

思路：利用 Python 的自带的语法解析模块 ast 模块把中序表达式解析成抽象语法树（AST，Abstract Syntax Tree），把原本需要自己写“运算符优先级”和“栈”的问题，交给 Python 的语法分析器自动完成。然后递归遍历语法树，按照“左子树 → 右子树 → 根节点”的顺序输出，这正是 后序遍历 的顺序，也正对应 后缀表达式 的结构。

mode='eval' 让 ast.parse() 解析的是“单个表达式”，不会把它当成程序。

返回的 tree 是 ast.Expression 对象；

真正的表达式节点（BinOp / Constant）在 tree.body 里，所以我们要从 tree.body 开始递归遍历。

ast 中的运算符是类（如 ast.Add, ast.Mult），需要映射成我们要打印的符号 "+"、"-"、"*"、"/"。

python

import ast

# 定义运算符到字符串的映射
operator_to_str = {
 ast.Add: '+',
 ast.Sub: '-',
 ast.Mult: '*',
 ast.Div: '/'
}

def postfix(node):
 # 如果节点是常量，则直接返回其值
 if isinstance(node, ast.Constant):
     return str(node.value)
 # 如果节点是二元运算符，则递归处理左右子节点并拼接运算符
 elif isinstance(node, ast.BinOp):
     return f'{postfix(node.left)} {postfix(node.right)} {operator_to_str[type(node.op)]}'

# 主程序部分
n = int(input())
for i in range(n):
 expr = input()
 tree = ast.parse(expr, mode='eval')
 print(postfix(tree.body))

对照示意图：

tree = ast.parse("3+4.5*(7+2)", mode='eval')

结构：

Expression
└── body → BinOp(+)
      ├── left: Constant(3)
      └── right: BinOp(*)
              ├── left: Constant(4.5)
              └── right: BinOp(+)
                      ├── left: Constant(7)
                      └── right: Constant(2)

调用：

postfix(tree.body)

从 BinOp(+) 开始递归，就能正确生成：

3 4.5 7 2 + * +

T24591: 中序表达式转后序表达式 ​

T24591: 中序表达式转后序表达式