栈
2019-01-03 本文已影响0人
疯了个魔
栈一种线性有序的数据元素集合，它的特点是，数据的增加删除操作都在同一端进行。进行操作的这一端，我们一般叫做“顶”，另一端叫做“底”。
最新进入的数据总是最先被移走，这叫做LIFO(Last in first out)。
栈的结构类似下面书的堆放，要想拿到下面的书，就要先取走上面的书，最后被放上的书，最先被取走。
图书“栈”
栈的抽象数据类型
栈的操作方法如下：
| 操作 | 描述 | 返回值 |
|---|---|---|
| Stack() | 构造方法，创建一个空栈，无参数 | 空栈 |
| push(item) | 向栈顶压入一个新数据项，需要一个数据项参数 | 无返回值 |
| pop() | 抛出栈顶数据项，栈本身发生变化，无参数 | 被抛出的栈顶元素 |
| peek() | 返回栈顶数据项，但不删除，栈不变 | 栈顶元素 |
| isEmpty() | 测试栈是否空栈，不需要参数 | 布尔值 |
| size() | 返回栈内数据项的数目，不需要参数 | 返回值是整数 |
python实现栈
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.items:
return self.items.pop()
else:
return None
def peek(self):
if self.items:
return self.items[-1]
else:
return None
def size(self):
return len(self.items)
下面的程序是对stack的简单测试：
s = Stack()
print(s.isEmpty()) #True
s.push(4)
s.push('dog')
print(s.peek()) #dog
s.push(True)
print(s.size()) #3
print(s.isEmpty()) #False
s.push(8.4)
print(s.pop()) #8.4
print(s.pop()) #True
print(s.size()) #2
栈的应用
简单括号匹配
括号匹配意味着每个开始符号具有相应的结束符号，并且括号能被正确嵌套。
正确匹配的括号字符串：
(()()()())
(((())))
(()((())()))
不匹配的括号：
((((((())
()))
(()()(()
如下图所示，从左到右处理符号时，最近开始符号必须与下一个关闭符号相匹配；此外，处理的第一个开始符号必须等待直到其匹配最后一个符号。
简单括号匹配
解题思路：
- 创建一个空栈；
- 从左到右开始处理字符串，如果是"("将其入栈，如果是")",这时栈如果为空，就失配，否则从栈中弹出一个元素；
- 当所有符号都被处理后，栈应该是空的。
def parChecker(SymbolString):
s = Stack()
balanced = True
index = 0
while index < len(SymbolString) and balanced:
symbol = SymbolString[index]
if symbol == '(':
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
s.pop()
index += 1
if balanced and s.isEmpty():
return True
else:
return False
符号匹配
匹配的符号：
{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }
不匹配的符号：
( [ ) ]
( ( ( ) ] ) )
[ { ( ) ]
解题思路：
与上面简单括号的解题思路基本类似，当遇到“结束符号”时，从栈中取出一个元素，并且这两个元素必须能够匹配，否则就失配。
#符号匹配
def matches(open,close):
opens = "([{"
closes = ")]}"
return opens.index(open) == closes.index(close)
def symbolMatch(SymbolString):
s = Stack()
balanced = True
index = 0
while index < len(SymbolString) and balanced:
symbol = SymbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index += 1
if balanced and s.isEmpty():
return True
else:
return False
十进制转换成二进制
如下图所示，将十进制转换成二进制就是不断迭代的将十进制除以 2，并跟踪余数。
十进制转换成二进制
def divideBy2(decNumber):
remstack = Stack()
while decNumber > 0:
rem = decNumber % 2
remstack.push(rem)
decNumber = decNumber // 2
binString = ""
while not remstack.isEmpty():
binString = binString + str(remstack.pop())
return binString
可以定义一个更加通用的，以十进制数和 2 到 16 之间的任何基数作为参数的函数：
def baseConverter(decNumber,base):
digits = "0123456789ABCDEF"
remstack = Stack()
while decNumber > 0:
rem = decNumber % base
remstack.push(rem)
decNumber = decNumber // base
newString = ""
while not remstack.isEmpty():
newString = newString + digits[remstack.pop()]
return newString
中缀，前缀和后缀表达式
- 中缀表达式：操作符以中缀形式处于操作数的中间，中缀表达式是人们常用的算术表示方法。
- 前缀表达式：又称为波兰式，前缀表达式的运算符位于两个相应操作数之前。
- 后缀表达式：又称为逆波兰式，后缀表达式的运算符位于两个相应操作数之后。
| 中缀表达式 | 前缀表达式 | 后缀表达式 |
|---|---|---|
| A+BxC+D | ++AxBCD | ABCx+D+ |
| (A+B)x(C+D) | x+AB+CD | AB+CD+x |
| AxB+CxD | +xABxCD | ABxCDx+ |
| A+B+C+D | +++ABCD | AB+C+D+ |
中缀表达式转换前缀和后缀
A+BxC可以写成(A+(BxC))，以明确标识乘法优先于加法，圆括号对的位置实际上是包含的运算符的最终位置的线索。
上面的子表达式（BxC）中的右括号， 如果我们将乘法符号移动到那个位置，并删除匹配的左括号，得到 BCx，我们实际上已经将子表达式转换为后缀符号。 如果加法运算符也被移动到其相应的右括号位置并且匹配的左括号被去除，则将得到完整的后缀表达式：
中缀表达式转换成后缀表达式
如果将符号移动到左括号的位置，我们得到前缀表达式：
中缀表达式转换成前缀表达式
所以为了转换表达式，无论是对前缀还是后缀符号，先根据操作的顺序把表达式转换成完全括号表达式。然后将包含的运算符移动到左或右括号的位置，具体取决于需要前缀或后缀符号。
例如：
中缀表达式转换成前缀/后缀表达式
中缀转后缀表达式的通用算法
假设中缀表达式是一个由空格分隔的标记字符串。 操作符标记是x，/，+和 - ，以及左右括号。操作数是单字符 A，B，C 等。 以下步骤将后缀顺序生成后缀表达式字符串：
- 创建一个名为 opstack 的空栈以保存运算符，给输出创建一个空列表。
- 通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
- 从左到右扫描标记列表。
- 如果标记是操作数，将其附加到输出列表的末尾。
- 如果标记是左括号，将其压到 opstack 上。
- 如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
- 如果标记是运算符，x，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
- 当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
下图展示了A * B + C * D转换成后缀表达式的过程：
中缀表达式转换成后缀表达式
python 实现：
# 中缀表达式转换成后缀表达式
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]):
postfixList.append(opStack.pop())
opStack.push(token)
#字符串遍历完成后，将栈中剩余的元素依次添加到列表中
while not opStack.isEmpty():
postfixList.append(opStack.pop())
#组成新的以空格分隔的字符串
return " ".join(postfixList)
后缀表达式求值
假设后缀表达式是一个由空格分隔的标记字符串。 运算符为x，/，+和 - ，操作数假定为单个整数值。 输出将是一个整数结果。
- 创建一个名为 operandStack 的空栈。
- 拆分字符串转换为标记列表。
- 从左到右扫描标记列表。
- 如果标记是操作数，将其从字符串转换为整数，并将值压到operandStack。
- 如果标记是运算符x，/，+或-，它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数，第二个弹出的是第一个操作数。执行算术运算后，将结果压到操作数栈中。
- 当输入的表达式被完全处理后，结果就在栈上，弹出 operandStack 并返回值。
例如，计算4 5 6 * +表达式的过程可以描述如下图所示：
后缀表达式求值
后缀表达式求值
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
