Python栈及常见应用
- # Python3.5
- # 定义一个栈类
- class Stack():
- # 栈的初始化
- def __init__(self):
- self.items = []
- # 判断栈是否为空,为空返回True
- def isEmpty(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[len(self.items)-1]
- # 判断栈的大小
- def size(self):
- return len(self.items)
-
- # 栈属性测试
- # 测试数据
- # s = Stack()
- # print(s.isEmpty())
- # s.push(4)
- # s.push('dog')
- # print(s.peek())
- # s.push(True)
- # print(s.isEmpty())
- # s.push(8.4)
- # print(s.pop())
- # print(s.pop())
- # print(s.size())
-
- # 利用栈将字串的字符反转
- def revstring(mystr):
- # your code here
- s = Stack()
- outputStr = ''
- for c in mystr:
- s.push(c)
- while not s.isEmpty():
- outputStr += s.pop()
- return outputStr
-
- # print(revstring('apple'))
- # print(revstring('x'))
- # print(revstring('1234567890'))
-
- # 利用栈判断括号平衡Balanced parentheses
- 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 = s.pop()
- if not matches(top, symbol):
- balanced = False
- index += 1
-
- if balanced and s.isEmpty():
- return True
- else:
- return False
-
- def matches(open, close):
- opens = '([{'
- closers = ')]}'
- return opens.index(open) == closers.index(close)
-
- # print(parChecker('({([()])}){}'))
-
- # 利用栈将十进制整数转化为二进制整数
- def Dec2Bin(decNumber):
- s = Stack()
-
- while decNumber > 0:
- temp = decNumber % 2
- s.push(temp)
- decNumber = decNumber // 2
- binString = ''
- while not s.isEmpty():
- binString += str(s.pop())
- return binString
-
- # print(Dec2Bin(42))
-
- # 利用栈实现多进制转换
- def baseConverter(decNumber, base):
- digits = '0123456789ABCDEF'
-
- s = Stack()
-
- while decNumber > 0:
- temp = decNumber % base
- s.push(temp)
- decNumber = decNumber // base
-
- newString = ''
- while not s.isEmpty():
- newString = newString + digits[s.pop()]
-
- return newString
-
- # print(baseConverter(59, 16))
-
- # 利用栈实现普通多项式的后缀表达式
- 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)
-
- # print(infixToPostfix("A * B + C * D"))
- # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。