数据结构与算法之栈Stack

线性数据结构（linear data structure）第一讲栈（stack）

栈的添加和移除原则为：后入先出（last-in first-out, LIFO）。生活中书桌上的一摞书、浏览网页时返回键，这里都有栈的概念。

栈的操作：

• Stack() 创建一个新栈，返回空的栈。
• push(item) 在栈的顶部添加一个元素，返回None。
• pop() 从栈的顶部移除一个元素，返回移除的元素。
• peek() 返回栈顶部元素，不从栈中移除。
• is_empty() 判断栈是否为空，返回True或者False。
• size() 返回栈中元素个数。

栈的实现[1]：

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]
    def size(self):
        return len(self.items)

栈的优点：

• 操作很快。无论栈大还是小，基本操作都离不开对栈顶上数据的操作。

栈的用处：

• 符号匹配
• 深度优先搜索中用于记录将要被访问的节点
• 前缀、中缀、后缀表达式

判断是否是需要用栈：看场景里面有没有 LIFO、reverse的需求 - myself : )

符号匹配

问题描述：输入一个字符串，判断字符串中{、}、[、]、(、)符号是否正确[2]，并返回True或者False。

解决思路：遇到开合符号存入栈，遇到闭合符号检查是否和栈顶符号match。正确情况下处理结束时，栈应该为空。

def is_valid(input_string):
    stack = Stack()
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in input_string:
        if ch in pairs.values():
            stack.push(ch)
        elif ch in pairs:
            if stack.is_empty() or stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()
>>> assert(is_valid('{ { ( [ ] [ ] ) } ( ) }')) == True

中缀、前缀、后缀表达式

问题描述：将中缀表达式转换成前缀、后缀表达式[3]。

解决思路：

• 在转换为后缀表达式时将操作符压入栈
  • 操作符有优先级；
  • 当遇到)时，应该在栈中一直找到(，其中(和)都不会保留。
  • 当遇到优先级小的操作符时，应该在栈中一直pop直到找到比它优先级低的操作符；
  • 最后栈中操作符应该全部被取出。
• 在转换为前缀表达式时将操作数和操作符压入不同的栈
  • 当遇到优先级更低的操作符，把操作符和操作数组合成新的操作数，存起来 new_operand
  • 最后操作符栈中为空，操作数栈中应该只有一个元素，最终结果

def infix_to_postfix(expr):
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    op_stack = Stack()
    postfix_list = []

    for token in expr.split():
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            postfix_list.append(token)
        elif token == '(':
            op_stack.push(token)
        elif token == ')':
            while op_stack.peek() != '(':
                postfix_list.append(op_stack.pop())
        else:
            while not op_stack.is_empty() and \
                prec[op_stack.peek()] >= prec[token]:
                    postfix_list.append(op_stack.pop())
            op_stack.push(token)
    while not op_stack.is_empty():
        postfix_list.append(op_stack.pop())
    return ' '.join(postfix_list)
>>> assert(infix_to_postfix('A * B + C * D')) == 'A B * C D * +'
>>> assert(infix_to_postfix('( A + B ) * C - ( D - E ) * ( F + G )')) == 'A B + C * D E - F G + * -'

def infix_to_prefix(expr):
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    operator_stack = Stack()
    operand_stack = Stack()

    def new_operand(operator_s, operand_s):
        oper = operator_s.pop()
        right = operand_s.pop()
        left = operand_s.pop()
        return ' '.join([oper, left, right])

    for token in expr.split():
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            operand_stack.push(token)
        elif token == ')':
            while operator_stack.peek() != '(':
                operand_stack.push(new_operand(operator_stack, operand_stack))
            operator_stack.pop() # pop '('
        elif operator_stack.is_empty() or token == '(' or prec[token] > prec[operator_stack.peek()]:
            operator_stack.push(token)
        elif prec[token] <= prec[operator_stack.peek()]:
            while not operator_stack.is_empty() and prec[token] <= prec[operator_stack.peek()]:
                operand_stack.push(new_operand(operator_stack, operand_stack))
            operator_stack.push(token)

    while not operator_stack.is_empty():
        operand_stack.push(new_operand(operator_stack, operand_stack))

    return operand_stack.peek()
>>> print infix_to_prefix('A + B')
+ A B
>>> print infix_to_prefix('A + B * C')
+ A * B C
>>> print infix_to_prefix('( A + B ) * C')
* + A B C
>>> print infix_to_prefix('A + B * C + D')
+ + A * B C D
>>> print infix_to_prefix('( A + B ) * ( C + D )')
* + A B + C D
>>> print infix_to_prefix('A * B + C * D')
+ * A B * C D
>>> print infix_to_prefix('A + B + C + D')
+ + + A B C D

参考资料：

• Problem Solving with Algorithms and Data Structures - Chapter 3
• Data Structures Reference - For coding interviews or computer science classes
• Github - Python - 数据结构和算法实现

注[1]: 重点知道数据结构有哪些操作。在实现上没有考虑pop前检查栈是不是为空等。参考资料3中后多种实现。

注[2]: 开合符号和闭合符号有正确的对应关系。

{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }

注[3]: 中缀是指操作符在两个操作数中间，好比A + B。如果将操作符移到两个操作数之前，表达式则被改写为+ A B这种前缀的形式。同理，后缀的形式为A B +。将中缀改为前缀或后缀的好处是，前缀和后缀表达式可以在没有括号的情况下依旧准确的表达复杂表达式的计算顺序。更多说明可以参见，参考资料1中3.9章节。如+ + A * B C D此类前缀表达式，只需在遇到操作符后有两个操作数的时候执行计算。 + + A (B * C) D -> + (A + (B * C)) D -> ((A + (B * C)) + D)