Python栈及常见应用

本文阅读 1 分钟
首页 Python笔记 正文
  1. # Python3.5
  2. # 定义一个栈类
  3. class Stack():
  4. # 栈的初始化
  5. def __init__(self):
  6. self.items = []
  7. # 判断栈是否为空,为空返回True
  8. def isEmpty(self):
  9. return self.items ==[]
  10. # 向栈内压入一个元素
  11. def push(self, item):
  12. self.items.append(item)
  13. # 从栈内推出最后一个元素
  14. def pop(self):
  15. return self.items.pop()
  16. # 返回栈顶元素
  17. def peek(self):
  18. return self.items[len(self.items)-1]
  19. # 判断栈的大小
  20. def size(self):
  21. return len(self.items)
  22. # 栈属性测试
  23. # 测试数据
  24. # s = Stack()
  25. # print(s.isEmpty())
  26. # s.push(4)
  27. # s.push('dog')
  28. # print(s.peek())
  29. # s.push(True)
  30. # print(s.isEmpty())
  31. # s.push(8.4)
  32. # print(s.pop())
  33. # print(s.pop())
  34. # print(s.size())
  35. # 利用栈将字串的字符反转
  36. def revstring(mystr):
  37. # your code here
  38. s = Stack()
  39. outputStr = ''
  40. for c in mystr:
  41. s.push(c)
  42. while not s.isEmpty():
  43. outputStr += s.pop()
  44. return outputStr
  45. # print(revstring('apple'))
  46. # print(revstring('x'))
  47. # print(revstring('1234567890'))
  48. # 利用栈判断括号平衡Balanced parentheses
  49. def parChecker(symbolString):
  50. s = Stack()
  51. balanced = True
  52. index = 0
  53. while index < len(symbolString) and balanced:
  54. symbol = symbolString[index]
  55. if symbol in '([{':
  56. s.push(symbol)
  57. else:
  58. if s.isEmpty():
  59. balanced = False
  60. else:
  61. top = s.pop()
  62. if not matches(top, symbol):
  63. balanced = False
  64. index += 1
  65. if balanced and s.isEmpty():
  66. return True
  67. else:
  68. return False
  69. def matches(open, close):
  70. opens = '([{'
  71. closers = ')]}'
  72. return opens.index(open) == closers.index(close)
  73. # print(parChecker('({([()])}){}'))
  74. # 利用栈将十进制整数转化为二进制整数
  75. def Dec2Bin(decNumber):
  76. s = Stack()
  77. while decNumber > 0:
  78. temp = decNumber % 2
  79. s.push(temp)
  80. decNumber = decNumber // 2
  81. binString = ''
  82. while not s.isEmpty():
  83. binString += str(s.pop())
  84. return binString
  85. # print(Dec2Bin(42))
  86. # 利用栈实现多进制转换
  87. def baseConverter(decNumber, base):
  88. digits = '0123456789ABCDEF'
  89. s = Stack()
  90. while decNumber > 0:
  91. temp = decNumber % base
  92. s.push(temp)
  93. decNumber = decNumber // base
  94. newString = ''
  95. while not s.isEmpty():
  96. newString = newString + digits[s.pop()]
  97. return newString
  98. # print(baseConverter(59, 16))
  99. # 利用栈实现普通多项式的后缀表达式
  100. def infixToPostfix(infixexpr):
  101. prec = {}
  102. prec['*'] = 3
  103. prec['/'] = 3
  104. prec['+'] = 2
  105. prec['-'] = 2
  106. prec['('] = 1
  107. opStack = Stack()
  108. postfixList = []
  109. tokenList = infixexpr.split()
  110. for token in tokenList:
  111. if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
  112. postfixList.append(token)
  113. elif token == '(':
  114. opStack.push(token)
  115. elif token == ')':
  116. topToken = opStack.pop()
  117. while topToken != '(':
  118. postfixList.append(topToken)
  119. topToken = opStack.pop()
  120. else:
  121. while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
  122. postfixList.append(opStack.pop())
  123. opStack.push(token)
  124. while not opStack.isEmpty():
  125. postfixList.append(opStack.pop())
  126. return ''.join(postfixList)
  127. # print(infixToPostfix("A * B + C * D"))
  128. # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python实现希尔排序
« 上一篇 01-21
Python分治算法
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18474 篇
  • 评论总数:
    53223 条
  • 标签总数:
    8841 个
  • 总浏览量:
    21065101 次
  • 最后更新:
    2024年12月07日

最多点赞

随便看看

标签TAG