简介
本文介绍两种转换方式，任意进制转换和表达式转换。
1 其他的进制转换方法
二 任意进制(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 表达式转换
中缀表达式。A*B 类似这样，操作符介于操作数 operabd 中间的表示法，称为 中缀 表示法
有括号时，括号表示强制优先级，嵌套括号中，内层优先级更高
以操作符相对于操作数的位置来定义，
前缀表达式。+AB， A+BC 的前缀表达式为 +ABC
后缀表达式。AB+, A+BC 的后缀表达式为 ABC+
中缀 转换为前缀或后缀表达式两个步骤：
1，中缀表达式 转换为 全括号形式
2，把运算符移到 左括号(前缀) 或 右括号(后缀)并替换，然后删除所有括号即可。
依据以上规则，我们定义如下字典，分别映射对应其优先级：
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
3 表达式转换完整代码
输入参数为需要转换的 表达式字符串：
@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)
4 程序完整代码
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)
5 小结
这里我们比较完整地归集了一些堆的基本应用例子。主要介绍两种转换方法：
1) 任意进制转换，通过将数字从源进制转为10进制，再转为目标进制，支持2到36进制间的转换；
2) 中缀表达式到后缀表达式的转换，用于解决运算符优先级问题，通过全括号形式和堆来实现。
还提供了完整的Python代码实现，包括进制转换函数transfAny和中缀到后缀表达式转换的infixToPostfix函数。
