数据结构[Python--Stack] 的应用
from __future__ import divisionclass Node():
def __init__(self, value):
self.value = value
self.next = None
class StackNode():
def __init__(self):
self.top = None
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
def pop(self):
node = self.top
self.top = node.next
return node.value
def compute_exec(op, ov1, ov2):
def add(ov1, ov2):
return ov1 + ov2
def sub(ov1, ov2):
return ov1 - ov2
def mul(ov1, ov2):
return ov1 * ov2
def div(ov1, ov2):
return ov1 / ov2
ops = {add: '+', sub: '-', mul: '*', div: "/"}
for k, v in ops.items():
if v == op:
ret = k(ov1, ov2)
stack1.push(ret)
break
def perfix_reverse(string):# reverse
tmp = ''
for s in string[::-1]:
if s == "(":
tmp += ")"
elif s == ")":
tmp += "("
else:
tmp += s
return tmp
def infix_to_prefix(string):
opt = ''
string_tmp = perfix_reverse(string)
for i in string_tmp:#前缀表达式
if i.isdigit():
opt = i + opt
elif i != ')':
stack1.push(i)
elif i == ")":
opt = stack1.pop() + opt
stack1.pop()
for s in opt[::-1]:
if s.isdigit():
stack1.push(s)
else:
op1 = s
ov1 = stack1.pop()
ov2 = stack1.pop()
compute_exec(op1, int(ov1), int(ov2))# compute result
continue
return opt, stack1.pop()
if __name__ == '__main__':
stack1 = StackNode()# 操作符
infix = ['((3+4)*2)', '((3+(4*2))-1)', '(5*(1+2))']
for i, v in enumerate(infix):
print infix, "==>", infix_to_prefix(v)
页:
[1]