python实现逆波兰计算表达式，python波兰表达式,逆波兰表达式又叫做后缀表

python实现逆波兰计算表达式，python波兰表达式,逆波兰表达式又叫做后缀表

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

如下python实现的逆波兰表达式：

[Python]代码

# -*- coding: utf-8 -*-symbol_priority = {}symbol_priority[0] = ['#']symbol_priority[1] = ['(']symbol_priority[2] = ['+', '-']symbol_priority[3] = ['*', '/']symbol_priority[4] = [')']def comparePriority(symbol, RPN_stack, symbol_stack):    '''Compare priority between two symbols'''    global symbol_priority    if len(symbol_stack) > 0:        symbol_pop = symbol_stack.pop()    else:        return    for list in symbol_priority.values():        if (symbol in list) and (symbol_pop in list):            '''same priority'''            symbol_stack.append(symbol_pop)            symbol_stack.append(symbol)            return        elif symbol in list:            '''symbol is smaller'''            RPN_stack.append(symbol_pop)            #recusion call            comparePriority(symbol, RPN_stack, symbol_stack)            return        elif symbol_pop in list:            '''symbol is bigger'''            symbol_stack.append(symbol_pop)            symbol_stack.append(symbol)            return        else:            continue        symbol_stack.append(symbol_pop)        returndef scanEveryone(input_string, RPN_stack, symbol_stack):    for ch in input_string:        if ch.isdigit():            RPN_stack.append(ch)        else:            if len(symbol_stack) > 0:                if ch == '(':                    symbol_stack.append(ch)                elif ch == ')':                    while True:                        symbol_pop = symbol_stack.pop()                        if symbol_pop == '(':                            break                        else:                            RPN_stack.append(symbol_pop)                else:                    comparePriority(ch, RPN_stack, symbol_stack)            else:                symbol_stack.append(ch)def scanInput(RPN_stack, symbol_stack):    input_string = raw_input()    input_string += '#'    scanEveryone(input_string, RPN_stack, symbol_stack)def calRPN(RPN_stack):    value_stack = []    RPN_stack.append('#')    for value in RPN_stack:        if value == '#':            return value_stack.pop()            break        if value.isdigit():            value_stack.append(value)        else:            right_value = value_stack.pop()            left_value = value_stack.pop()            cal_string = left_value + value + right_value            value_stack.append(str(eval(cal_string)))def main():    RPN_stack = []    symbol_stack = []    scanInput(RPN_stack, symbol_stack)    print calRPN(RPN_stack)if __name__ == '__main__':    main()

calRPN.py

# -*- coding: utf-8 -*-symbol_priority = {}symbol_priority[0] = ['#']symbol_priority[1] = ['(']symbol_priority[2] = ['+', '-']symbol_priority[3] = ['*', '/']symbol_priority[4] = [')']def comparePriority(symbol, RPN_stack, symbol_stack):    '''Compare priority between two symbols'''    global symbol_priority    if len(symbol_stack) > 0:        symbol_pop = symbol_stack.pop()    else:        return    for list in symbol_priority.values():        if (symbol in list) and (symbol_pop in list):            '''same priority'''            symbol_stack.append(symbol_pop)            symbol_stack.append(symbol)            return        elif symbol in list:            '''symbol is smaller'''            RPN_stack.append(symbol_pop)            #recusion call            comparePriority(symbol, RPN_stack, symbol_stack)            return        elif symbol_pop in list:            '''symbol is bigger'''            symbol_stack.append(symbol_pop)            symbol_stack.append(symbol)            return        else:            continue        symbol_stack.append(symbol_pop)        returndef scanEveryone(input_string, RPN_stack, symbol_stack):    for ch in input_string:        if ch.isdigit():            RPN_stack.append(ch)        else:            if len(symbol_stack) > 0:                if ch == '(':                    symbol_stack.append(ch)                elif ch == ')':                    while True:                        symbol_pop = symbol_stack.pop()                        if symbol_pop == '(':                            break                        else:                            RPN_stack.append(symbol_pop)                else:                    comparePriority(ch, RPN_stack, symbol_stack)            else:                symbol_stack.append(ch)def scanInput(RPN_stack, symbol_stack):    input_string = raw_input()    input_string += '#'    scanEveryone(input_string, RPN_stack, symbol_stack)def calRPN(RPN_stack):    value_stack = []    RPN_stack.append('#')    for value in RPN_stack:        if value == '#':            return value_stack.pop()            break        if value.isdigit():            value_stack.append(value)        else:            right_value = value_stack.pop()            left_value = value_stack.pop()            cal_string = left_value + value + right_value            value_stack.append(str(eval(cal_string)))def main():    RPN_stack = []    symbol_stack = []    scanInput(RPN_stack, symbol_stack)    print calRPN(RPN_stack)if __name__ == '__main__':    main()