• 欢迎光临~

3.栈的应用

• 1.简单括号匹配
• 2.十进制转换为二进制
• 3.十进制转换为十六以下任意进制代码
• 4.通用的中缀转后缀算法
• 5.后缀表达式求值

1.简单括号匹配

``````'''

'''

from pythonds.basic.stack import Stack  # pip install pythonds  栈的python模块，也可自己实现一个栈

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 = index +1

if balanced and s.isEmpty():
return True
else:
return False

print(parChecker('((()))')) # True
print(parChecker('(()()(()))')) # True

print(parChecker('(()')) # False
``````

``````# 更多种括号的匹配

'''

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

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

'''
from pythonds.basic.stack import Stack  # pip install pythonds  栈的python模块，也可自己实现一个栈

def parChecker(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 = matchs(symbol,s)
if top:
s.pop()
else:
balanced = False

index = index +1

if balanced and s.isEmpty():
return True
else:
return False

def matchs(symbol,s):
s_symbol =s.peek() # peek():"窥视"栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
if symbol == ")":
if s_symbol == "(":
return True
else:
return False
if symbol == "}":
if s_symbol == "{":
return True
else:
return False
if symbol == "]":
if s_symbol == "[":
return True
else:
return False

print(parChecker('((()))')) # True
print(parChecker('(()()(()))')) # True
print(parChecker("[{()]}")) # False
``````
``````此外，HTML/XML文档也有类似于括号的开闭标记，这种层次结构化文档的校验、操作也可以通过栈来实现
``````

``````# python3 code to check for balanced parentheses in an expression
def check(expression):
open_tup = tuple('({[')
close_tup = tuple(')}]')
map = dict(zip(open_tup,close_tup))
queue = []

for i in expression:
if i in open_tup:
queue.append(map[i])
elif i in close_tup:
if not queue or i != queue.pop():
return "Unbalanced"

if not queue:
return "Balanced"

else:
return "Unbalanced"

# Driver code
string = "{[]{()}}"
print(string, "-",check(string))

string = "((()"
print(string, "-", check(string))
``````

2.十进制转换为二进制

``````'''
“除以2”的过程，得到的余数是从低到高的次序，而输出则是从高到低，所以需要一个栈来反转次序
'''
``````

``````from pythonds.basic.stack import Stack

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

print(divideBy2(42)) # 101010
``````

3.十进制转换为十六以下任意进制代码

``````from pythonds.basic.stack import Stack

def baseConberter(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

print(baseConberter(25,2))  # 11001
print(baseConberter(25,16)) # 19
``````

4.通用的中缀转后缀算法

``````在中缀表达式转换为后缀形式的处理过程中，操作符比操作数要晚输出，所以在扫描到对应的第二个操作数之前，需要把操作符先保存起来，而这些暂存的操作符，由于优先级的规则，还有可能要反转的次序输出。

``````
``````后面的算法描述中，约定中缀表达式是由空格隔开的一系列单词（token）构成，操作符单词包括*/+-(),而操作数单词则是单词字母标识符A、B、C等。

A+B*C = split=> ["A","+","B","*","C"]

# 从左到右扫描中缀表达式单词列表

``````

``````以 (A+B)*(C+D)

from pythonds.basic.stack import Stack

from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):
prec = {}
prec['*'] = 3
prec['/'] = 3
prec['+'] = 2
prec['-'] = 2
prec['('] = 1
opStack = Stack()
postfix_list = []
tokenList = list(infixexpr)

print(tokenList) # ['(', 'A', '+', 'B', ')', '*', '(', 'C', '+', 'D', ')']

for token in tokenList:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
postfix_list.append(token)
elif token == "(":
opStack.push(token)
elif token == ")": # 当碰到右括号不断的弹出栈顶操作符，直到找到左括号
topToken = opStack.pop()
while topToken != '(':
postfix_list.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
postfix_list.append(opStack.pop())
opStack.push(token)

while not opStack.isEmpty():
postfix_list.append(opStack.pop())
print(postfix_list) # ['A', 'B', '+', 'C', 'D', '+', '*']
return ''.join(postfix_list)

print(infixToPostfix('(A+B)*(C+D)'))  # AB+CD+*
``````

5.后缀表达式求值

``````跟中缀转换为后缀问题不同，在对后缀表达式从左到右扫描的过程中，由于操作符在操作数的后面，所以要暂存操作数，在碰到操作符的时候，再将暂存的两个操作数进行实际的计算。

``````

``````创建空栈operandStack用于暂存操作数

``````
``````from pythonds.basic.stack import Stack
def postfixEval(postfixExpr):

operandStack = Stack()
tokenList = list(postfixExpr)

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('456+*'))  # 44
print(postfixEval('45+6*'))   # 54
``````