python栈的两个应用

1、进制转换

#!/usr/bin/env python3
# encoding: utf-8

import Stack # As previously defined

def divide_by_2(dec_number):
    rem_stack = Stack.Stack()

    while dec_number > 0:
        rem = dec_number % 2;
        rem_stack.push(rem)
        dec_number = dec_number // 2

    bin_string = ""
    while not rem_stack.is_empty():
        bin_string = bin_string + str(rem_stack.pop())

    return bin_string

def base_converter(dec_number, base):
    digits = "0123456789ABCDEF"

    rem_stack = Stack.Stack()

    while dec_number > 0:
        rem = dec_number % base 
        rem_stack.push(rem)
        dec_number = dec_number // base 

    new_string = ""
    while not rem_stack.is_empty():
        new_string = new_string + digits[rem_stack.pop()]
    return new_string

if __name__ == "__main__":
    print(divide_by_2(42))
    print(base_converter(42, 2))
    print(base_converter(25, 16))



    

　　2、中缀表达式变后缀表达式

#!/usr/bin/env python3
# encoding: utf-8

import Stack # As previously defined

def infix_to_postfix(infix_expr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1

    op_stack = Stack.Stack()
    postfix_list = []
    token_list = infix_expr.split()
    #print(token_list)
    for token in token_list:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfix_list.append(token)
        elif token == '(':
            op_stack.push(token)
        elif token == ')':
            top_token = op_stack.pop()

            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            while (not op_stack.is_empty()) and (prec[op_stack.peek()] >= prec[token]):
                postfix_list.append(op_stack.pop())
            op_stack.push(token)
    while not op_stack.is_empty():
        postfix_list.append(op_stack.pop())
    return "  ".join(postfix_list)

if __name__ == "__main__":
    print(infix_to_postfix("A * B + C * D"))
    print(infix_to_postfix("( A + B ) * C - ( D - E ) * ( F + G )"))

　　

　　3、后缀表达式求值

#!/usr/bin/env python3
# encoding: utf-8

import Stack

def postfix_eval(postfix_expr):
    operand_stack = Stack.Stack()
    token_list = postfix_expr.split()

    for token in token_list:
        if token in '0123456789':
            operand_stack.push(token)
        else:
            op2 = operand_stack.pop()
            op1 = operand_stack.pop()
            result = do_math(token, op1, op2)
            operand_stack.push(result)
    return operand_stack.pop()

def do_math(token, op1, op2):
    op1 = float(op1)
    op2 = float(op2)
    if token == '*':
        return op1 * op2 
    elif token == '/':
        return op1 /op2 
    elif token == '+':
        return op1 + op2 
    else:
        return op1 - op2

if __name__ == "__main__":
    print(postfix_eval('7 8 + 3 2 + /'))