注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

python实现逆波兰计算表达式

python 水墨上仙 2416次浏览 已收录 手机上查看

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

# -*- 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)
        return

def 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)
        return

def 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()


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明python实现逆波兰计算表达式
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……