逆波兰表达式求解四则运算式

python的内建函数eval能对四则运算的表达式进行求解,这里简单实现下模拟eval,当然没有实现的向eval那么复杂,现在只能处理所有数字均为个位数的四则运算表达式,表达式包括+,-,*,/,(,)和数字(0-9)。实现的过程很简单,就是借助了逆波兰表达式,先把四则运算表达式转换成逆波兰表达式,然后根据逆波兰表达式求解结果。

程序代码如下,代码中已经实现写了文档测试,可以多测几个:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

'Implementation of eval'

__author__ = 'iaccepted'

digits = [x for x in '0123456789']
priority = {'(':0, '+':1,'-':1,'*':2,'/':2}  #操作符的优先级

def parse(source):	#将表达式转换成逆波兰表达式
    '''
    >>> parse('9-2*2/2')
    [9, 2, 2, '*', 2, '/', '-']
    '''
    nibolan = []
    st = []            #一个栈
    for ch in source:  #遍历整个表达式的每个字符
        if ch == '(':
            st.append(ch)
        elif ch in digits:
            nibolan.append(int(ch))
        elif not st and ch in priority.keys():
            st.append(ch)
        elif st and ch in priority.keys():
            for x in range(st.__len__()):
                z=st[-1]
                p = priority[z]
                if p >= priority[ch]:
                    nibolan.append(st.pop())
                else:
                    break
            st.append(ch)
        elif ch == ')':
            for x in range(st.__len__()):
                if st[-1] == '(':
                    st.pop()
                    break
                else:
                    nibolan.append(st.pop())
    for x in range(st.__len__()):
        nibolan.append(st.pop())
    return nibolan

def ammd(a, b, op):   #add minus mul and divid-->ammd
	if op == '+':
		return a + b
	elif op == '-':
		return a - b
	elif op == '*':
		return a * b
	else:
		return a / b


def calculate(nibolan):    #传入转换后的逆波兰表达式
    '''
    >>> calculate('24-1*')
    -1
    '''
    nums = []
    for x in nibolan:
        if isinstance(x, (int, float)):
            nums.append(int(x))
            continue
        a=nums.pop()
        b=nums.pop()
        nums.append(ammd(b, a, x))
    return nums[0]



if __name__ == "__main__":
    #doctest -> successful
    #import doctest
    #doctest.testmod()
    source = "5/2+(3-1)*2-6*2"
    nibolan = parse(source)
    print(nibolan)
    result = calculate(nibolan)
    print('result:%s' % result)

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:逆波兰表达式求解四则运算式

本文链接地址:http://www.iaccepted.net/python/tutorial/52.html

相关文章



One thought on “逆波兰表达式求解四则运算式

发表评论

电子邮件地址不会被公开。 必填项已用*标注