中序转后序的算法 - 文祥

时间：2024-03-17 16:52:06

中序转后序的算法

平常所使用的表达式，主要是将操作数放在运操作数的两旁，例如a+b/d这样的式子，这称之为中序（Infix）表示式，对于人类来说，这样的式子很容易理解，但由于计算机执行指令时是有顺序的，遇到中序表示式时，无法直接进行运算，而必须进一步判断运算的先后顺序，所以必须将中序表示式转换为另一种表示方法。

可以将中序表示式转换为后序（Postfix）表示式，后序表示式又称之为逆向波兰表示式（Reverse polish notation），它是由波兰的数学家卢卡谢维奇提出，例如(a+b)*(c+d)这个式子，表示为后序表示式时是ab+cd+*。

用手算的方式来计算后序式相当的简单，将运算子两旁的操作数依先后顺序全括号起来，然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始），最后去掉所有的左括号就可以完成后序表示式，例如：

a+b*d+c/d   =>    ((a+(b*d))+(c/d)) -> abd*+cd/+

如果要用程序来进行中序转后序，则必须使用堆栈，算法很简单，直接叙述的话就是使用循环，取出中序式的字符，遇操作数直接输出；堆栈运算子与左括号；堆栈中运算子优先级大于读入的运算子优先级的话，直接输出堆栈中的运算子，再将读入的运算子置入堆栈；遇右括号输出堆栈中的运算子至左括号。

例如(a+b)*(c+d)这个式子，依算法的输出过程如下：

image

Python代码：

def priority(op):
    if op in [\'+\', \'-\']:
        return 1
    elif op in [\'*\', \'/\']:
        return 2
    else:
        return 0

def toPostfix(infix):
    stack = [\'\']
    buffer = []
    for c in infix:
        if c == \'(\':
            stack.append(c)
        elif c in "+-*/":
            while priority(stack[-1]) >= priority(c):
                buffer.append(stack.pop())
            stack.append(c)
        elif c == \')\':
            while stack[-1] != \'(\' && stack[-1] != \'\':
                buffer.append(stack.pop())
            stack.pop()
        else:
            buffer.append(c)
    while stack[-1] != \'\':
        buffer.append(stack.pop())
    return buffer

infix = "(a+b)*(c+d)"
print(toPostfix(infix))
print(toPrefix(infix))

相关文章