算法与数据结构

中缀前缀和后缀

栈的应用，中缀前缀和后缀。

中缀、前缀、后缀表达式

中缀、前缀、后缀表达式

20180410

优先级高的运算符在优先级低的运算符之前使用，唯一改变的是括号的存在。先乘除后加减。

正常的运算符在两个字符之间，称为中缀。 A+B

把运算符向前移，前缀。 + A B

运算符向后移动，后缀。 A B +

前缀表达式符号要求所有运算符在它们处理的两个操作数之前。另一方面，后缀表达式要求其操作符在相应的操作数之后。

案例1

中缀  A+B*C
前缀  +A*BC  过程 *优先于+  A+(*BC) -> +A*BC
后缀  ABC*+    过程 *优先于+   A+(BC*) (BC*)整体 -> ABC*+

案例2

存在括号。

中缀 (A+B)*C
前缀 (+AB)*C -> *+ABC
后缀 (AB+)*C -> AB+C*
中缀表达式转换前缀和后缀

使用特定方法可以让中缀转换为前缀和后缀。考虑使用算法来执行转换，允许任何复杂表达式转换。

使用的方法是用完全括号表达式的概念。比如 A + B * C写成 (A + (B * C))，明确标识乘法优先于加法。每个括号对还表示操作数对的开始和结束，中间有相应的运算符。

看到 (B * C)的右括号。将乘法移到那个位置，并删除对应的左括号。得到 B C *，实际上已经将其转换为后缀符号。如果加法运算符也移动到相应的位置并且删除匹配的左括号，将得到后缀表达式。

如果不是将符号移动到右括号的位置，将其向左移动，得到前缀符号。圆括号的位置实际是包含的运算符的最终位置的线索。

为了转换表达式，无论对前缀还是后缀，先根据操作的顺序把表达式转换成完全括号表达式。然后将包含的运算符移到左或右括号的位置，取决于需要前缀或后缀符号。

这里面有个更复杂的例子, (A + B) * C - (D - E) * (F + G) ， 以下显示了如何转换为后缀和前缀。

中缀转后缀通用法

开发一个算法将任何中缀表达式转换为后缀表达式。

A + B * C 转换为后缀为 A B C * +。

在后缀表达式中，+在结束位置，因为下一个运算符 *优先于加法。原始表达式中的运算符的顺序在生成的后缀表达式中相反。

由于加法运算符在乘法运算符之前，并且具有较低的优先级，因此需要在使用乘法运算符之后出现。这种顺序的反转，考虑使用栈来保存运算符直到使用它们。

带括号。

(A + B) * C 转换后缀表达式 A B + C *。

括号的优先级高于 *，转换算法的过程，当看到左括号时，保存它，表示高优先级的另一个运算符将出现。运算符需要等到相应的右括号出现以表示其位置。当右括号出现，可以从栈中弹出运算符。

从左到右扫描中缀表达式，将使用栈来保留运算符，栈堆的顶部将始终是最近保存的运算符。每当读取一个新的运算符时，需要考虑该运算符如何与已经在栈上的运算符(如果有的话)比较优先级。

假设中缀表达式是由空格分隔的标记字符串。操作符标记是 *,/,+ 和 -，以及左右括号，操作树是 A,B,C等。以下步骤将后缀顺序生成一个字符串。

  1. 创建一个名为 opstack的空栈以保存运算符。给输出创建一个空列表。
  2. 通过使用字符串方法拆分将输入的中缀字符串转换为标记列表

  3. 从左到右扫描标记列表

    • 如果是操作树，将其附加到输出列表的末尾
    • 如果是左括号，将其压到栈 opstack
    • 如果是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾
    • 如果标记是运算符， *,/,+ 或 -,将其压入 opstack。但是，首先删除已经在opstack中具有更高或相等优先级的运算符，将其加入输出列表中。

  4. 当输入表达式被完全处理时，检查opstack,仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。

对表达式A * B + C * D 的转换算法。注意，第一个 在看到 + 运算符时被删除。另外，当第二个 出现时， + 保留在栈中，因为乘法优先级高于加法。在中缀表达式的末尾，栈被弹出两次，删除两个运算符，并将 + 作为后缀表达式中的最后一个运算符。

使用一个名为prec的字典来保存运算符的优先级。这个字典将每个运算符映射到一个整数，可以与其他运算符的优先级进行比较。左括号被赋予最低值。这样与其进行比较的任何运算符都将具有更高的优先级，将放置它的顶部。

栈类

# -*- coding:utf-8 -*-
__author__ = '504'
__date__ = '2018/3/28 19:05'


# !/usr/bin/python
# ！ -*- coding:utf-8 -*-
class Stack:
    def __init__(self):
        self.items = []

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.isEmpty():
            raise IndexError
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items) - 1]  # 返回最后一个元素

    def size(self):
        return len(self.items)

具体代码

# -*- coding:utf-8 -*-
__author__ = '504'
__date__ = '2018/3/28 19:05'

from stack import Stack


def infixToPostfix(infixexpr):
    prec = {}  # 字典存储运算符优先级
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()  # 初始化栈
    postfixList = []  # 后缀列表
    tokenList = infixexpr.split()  # 中缀: 字符串--列表

    for token in tokenList:  # 遍历中缀列表
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)  # 操作数就入后缀列表
        elif token == '(':  # 遇到左括号入栈
            opStack.push(token)
        elif token == ')':  # 遇到右括号出栈
            topToken = opStack.pop()
            while topToken != '(':  # 当出栈不是左括号时,入后缀列表
                postfixList.append(topToken)
                topToken = opStack.pop()  # 出栈，直到是左括号

        else:
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):  #opStack.peek() 栈最后一个元素
                postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)


print infixToPostfix("A * B + C * D")
#print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
后缀表达式求值

每当在输入上看到运算符时，计算两个最近的操作数。

后缀表达式 4 5 6 * +

首先的操作数是 4 和 5，此时不确定如何处理，直到看到下一个符号，将其放置到栈上，确保它们在下一个运算符出现时可用。

4 和 5之后，下一个符号是操作数，放入栈中，压栈，并检测下一个符号，直到看到是 *，将栈中最近的操作数相乘。通过弹出两次栈，得到正确的操作数，然后执行乘法。 5 * 6 =30

稍微复杂的示例。

7 8 + 3 2 + /
后缀表达式的运算符的顺序没有改变，只是位置变了。当用于除法的操作数从栈弹出时，它们需要反转。 15/5和5/15不同，必须保证操作数的顺序不会变。

算法构思

假设后缀表达式是一个由空格分隔的标记字符串。运算符为 *,/,+和 -，操作数假定为单个整数值，输出是一个整数结果。

  1. 创建一个空栈 operandStack
  2. 拆分字符串为标记列表

  3. 从左到右扫描标记列表

    • 如果是数字，则转换为整数，入栈
    • 如果是 + - / * ，需要弹出栈中的两个数字，第一个弹出的为运算符右边的数字，第二个弹出的为左边。执行运算之后，将结果压入栈中

  4. 当输入的表达式被完全处理后，结果在栈上面，弹出即可。

    -- coding:utf-8 --

    author = ‘504’
    date = ‘2018/3/28 19:57’

    from stack import Stack

    def postfixEval(postfixExpr):

    operandStack = Stack()
tokenList = postfixExpr.split()

for token in tokenList:
    if token in "0123456789":
        operandStack.push(int(token))
    else:
        operand2 = operandStack.pop()
        operand1 = operandStack.pop()
        result = doMath(token,operand1,operand2)
        operandStack.push(result)
return operandStack.pop()

    执行算术运算

    def doMath(op,op1,op2):

    if op == "*":
    return op1 * op2
elif op == "/":
    return  op1 / op2
elif op == "+":
    return op1 + op2
else:
    return op1 - op2

    print postfixEval(‘7 8 + 3 2 + /‘)