使用堆栈进行后缀表达式转换，进制转换，符号合法性匹配
1 简介
堆栈的使用场景非常多，在很多编程语言虚拟机中都有应用，这里简单介绍几个使用场景。
2 使用场景
2.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.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
2.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 # 高位
2.4 转换代码
使用堆来处理逆序算法。
传入两个参数，需要判断的数字：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
2.5 转换的完整代码：
- 一 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
2.6 其他使用场景
将42转换为 2进制
print(divideBy2(42, 2))
将42转换为 8进制
print(divideBy2(42, 8))
将42转换为 16进制
print(divideBy2(42, 16))
2.7 其他的进制转换方法
- 二 任意进制(2~36)转换为10进制
本方法将 目标字符srcNum 转换为 10 进制，然后转换为 目标进制
将原字符M进制数，转换为10进制
将10进制转换为 目标进制 N 进制数
2 <= M,N <= 36
:params M, 原10 进制数, 表示原数据是多少进制的
:params N, 目标10 进制数, 表示原数据将要转换为多少进制
:params srcNum
def transfAny(M, N, srcNum):
src_list = list(str(srcNum))
ten_value = transfToTen(decNumber = srcNum, n=M)
dest_value = transform(decNumber = ten_value, dn=N)
return dest_value
n 表示字符的原进制
如果没有说明是几进制的，默认按10进制处理，栈来处理逆序算法 。
当目标字符串不为空，则不断取出，并取得字符在 原进制中表示多少值。
判断计算该位置表示多少，以10进制计。
累积10进制中的总数，
然后进入下一个字符的判断。
子函数，判断某个字符并取得字符表示 多少值
判断该值在进制范围内，否则报错
:param word 字符代表了10进制多少值
:param n 表示该字符属于几进制
def map_index(word, n):
dicmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
if word not in dicmap:
return False
else:
value = dicmap.index(word)
assert value <= n
return value
def transfToTen(decNumber, n=None):
dicmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
if not n:
n = 10
remstack = Stack()
dec_lis = list(str(decNumber))
destNum = 0
loop_n = 0
while len(dec_lis) > 0:
current_top = dec_lis.pop()
real_value = map_index(current_top, n)
sums = real_value * (n ** loop_n) #
destNum = destNum + sums
loop_n += 1 #
return destNum
2.9 表达式转换
中缀表达式。A*B 类似这样，操作符介于操作数 operabd 中间的表示法，称为 中缀 表示法
有括号时，括号表示强制优先级，嵌套括号中，内层优先级更高
以操作符相对于操作数的位置来定义，
前缀表达式。+AB， A+BC 的前缀表达式为 +ABC
后缀表达式。AB+, A+BC 的后缀表达式为 ABC+
中缀 转换为前缀或后缀表达式两个步骤：
1，中缀表达式 转换为 全括号形式
2，把运算符移到 左括号(前缀) 或 右括号(后缀)并替换，然后删除所有括号即可。
依据以上规则，我们定义如下字典，分别映射对应其优先级：
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
2.10 表达式转换的完整代码
输入参数为需要转换的 表达式字符串：
@param: infixexpr
解析表达式到单词列表
tokenList = list(infixexpr)
将表达式转换为列表，并进行遍历，如果在约定的字符内，则加入表达式字符列表中：
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())
print('peek postfixList:{}'.format(postfixList))
opStack.push(token)
逻辑处理的完整代码：
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)
2.11 程序完整代码
def infixToPostfix(infixexpr):
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = list(infixexpr)
words = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
nums = "0123456789"
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)
3 小结
这里我们比较完整地归集了一些堆的基本应用例子。
- 点赞
- 收藏
- 关注作者
评论（0）