数据结构[Python--Stack] 的应用

q6542125

from __future__ import division　　
class 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)