简介
本文介绍使用栈实现括号匹配和十进制转二进制的算法。并有完整代码示例和讲解说明。
1 成对匹配
比如括号验证，简单括号匹配。
栈也可以用于 XML,HTML的成对的关键字匹配校验。
括号一般用来指定表达式的运算优先级，多层括号的层级是否正确如，((()), ())))))。
规则，按栈的方式取值，第一个左括号 匹配 第一个右括号。
推广到 开闭校验，如 html。
我们将使用到 py中内置的一个函数，查找某个字符在 字符串中的序号，它就是 str 的index。
比如右括号是否与原 左括号匹配，它返回子串包含在 起始和结束位置。
选填参数 start，and 为子串切片的标记点。 如果是不支持的括号（即没有包含在可匹配字符中），将抛出错误。
def matched(op, cs):
opens = "([{"
closers = ")]}"
return opens.index(op) == closers.index(cs)
检查输入字符串中 右括号是否与原 左括号匹配。
我们首先定义一个堆栈。
s = Stack()
并且默认输入字符串是 平衡对称的匹配的。
balanced = True
并且开始遍历，当序号小于输入字符串长度，并且默认平衡因子为 true时，
我们获取字符串的当前序号的字符，并且判断如果字符在 目标待匹配括号时，将其压入堆中：
symb = symb_str[index]
if symb in "([{":
s.push(symb)
如果子字符不在目标匹配括号中，则进行调整：
如果堆为空，平衡因子设置为 false
if s.isEmpty():
balanced = False
否则，获取堆顶元素，并且与子字符进行匹配，不匹配，将平衡因子设置为 false，
while index < len(symb_str) and balanced:
symb = symb_str[index]
if symb in "([{":
s.push(symb)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matched(top, symb):
balanced = False
否则 index 加1，进行下一循环，如此对传入符号的进行全部匹配校验。
index = index + 1
如果全部字符都校验完成，平衡因子 仍然为 true，
而且堆已经全部取出校验，那么返回true，表示传入字符串时成对匹配的。
否则传入字符串不是成对匹配的，返回 false
if balanced and s.isEmpty():
return True
else:
return False
2 成对匹配完整代码：
简单括号成对匹配的完整代码。
def parChecker(symb_str):
s = Stack()
balanced = True
index = 0
while index < len(symb_str) and balanced:
symb = symb_str[index]
if symb in "([{":
s.push(symb)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matched(top, symb):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
3 十进制转化为二进制
人们常用的计算方法为 十进制，计算机计算方法为二进制。
高级语言算法 会经常对 十进制和二进制进行转换。
十进制转换为二进制，可采用的是 除以2求余数的算法。
将整数不断除以2，每次得到的余数就是由低到高 的二进制。
35 / 2 = 17 余 1 -- k0 # 低位
17 /2 = 8 余 1 -- k1
8/2 = 4 余 0 -- k2
4/2 = 2 余 0 -- k3
2/2 = 1 余 0 -- k4
1/2 = 0 余 1 -- k5 # 高位
3 转换代码
使用堆来处理逆序算法。
传入两个参数，需要判断的数字：decNumber， 和进制约定 n
10进制转换为2进制，默认参数
@params decNumber 要转换的数字
@params n 要转换为的进制，默认为2""
依照以上的原理，当待判断的数字不为0时，对其进行除以进制数，并将余数入堆。
最后把商赋予待处理数字。
while decNumber > 0:
rem = decNumber % n
remstack.push(rem)
decNumber = decNumber // n
最后取得相应的 进制组合成数字为最终结果
binString = ''
while not remstack.isEmpty():
binString = binString + digits[remstack.pop()]
return binString
4 完整代码：
一 10进制转换为任意进制(2~36)
此为第一个方法。
def divideBy2(decNumber, n=None):
digits = "0123456789ABCDEF" if not n: n = 2 remstack = Stack() while decNumber > 0: rem = decNumber % n remstack.push(rem) decNumber = decNumber // n binString = '' while not remstack.isEmpty(): binString = binString + digits[remstack.pop()] return binString
5 如何使用
将42转换为 2进制
print(divideBy2(42, 2))
将42转换为 8进制
print(divideBy2(42, 8))
将42转换为 16进制
print(divideBy2(42, 16))
