Pythonベースの逆ポーランド式の変換と評価

一、逆ポーランド式の概要
逆ポーランド式(Reverse Polish notation,RPN,または逆ポーランド記法)は、接尾辞式(演算子をオペランドの後に書く)とも呼ばれます.これに対応するのは、数学でよく見られる接尾辞式(オペレータがオペランドの間にいる場合もある)であり、例えば12+23が典型的な接尾辞式であり、それに対応する逆ポーランド式は12,13,+
二、用途
従来の接尾辞式を接尾辞式に変換すると,計算機の計算を簡略化することができる.複雑な式を、簡単な操作で計算結果を得ることができる式に変換します.コンピュータのプログラミングを容易に実現し、例えば(a+b)*(c+d)をab+cd+*に変換すると、括弧の演算が回避され、プログラミングと計算において論理判断と分岐の処理が少なくなる.
三、アルゴリズム
(一).ポーランド逆変換
まず2つの空きスタックを作成し(PythonでListでスタックを実現できる機能)、stack_expr, stack_oprはそれぞれオペランドとオペレータをインストールします.最初から準備した接頭辞式を遍歴し、以下の手順で変換します:(注:ここでは本人が接頭辞式をリスト形式に処理し、後続の計算を容易にし、読者が自分で接頭辞式形式を決定することができます)

             ： 2.0*(3.1+4.8)+5.0  ----> [2.0, '*', '(', 3.1, '+', 4.8, ')', '+', 5.0]

0、          Index
1、 index   ，   index  stack_expr
2、 index    ：
	2.1、    ，       stack_opr
	2.2、    ， stack_opr               stack_expr，            （  ：       stack_opr    stack_expr）               
	2.3、 index      （+ - * /）
		 2.3.1、  stack_opr  ，      stack_opr
		 2.3.2、   stack_opr  ， stack_opr      index     ：
				2.3.2.1、 index      stack_opr         ， index    stack_opr
				2.3.2.2、 index          stack_opr     ， stack_opr            stack_expr，  index     stack_opr     ， index stack_opr 。( ： stack_opr   , stack_opr   ，index      )
				
3、          stack_opr    ，            stack_expr

コード実装:

	pat = ['+','-','*','/','(',')','%']
	def reverse_polish(data):
		stack_opr = list()
		#   
		stack_expr = list()
		#   
		dicts = {
			'+' : 1,
			'-' : 1,
			'*' : 2,
			'/' : 2,
			'(' : 0
		}
	
		global pat
		
		for index in data:
			#1.  ， expr 
			if index not in pat:
				stack_expr.append(index)
			
			#2.   
			else:
				#2.1 opr  
				if	not stack_opr:
					stack_opr.append(index)
				#2.2 opr   
				else:
					#2.2.1 index       ,  opr
					if index == '(':
						stack_opr.append(index)
					#2.2.2 index     ,        opr ，  expr  ，       
					elif index ==')':
						while True:
							newdex = stack_opr.pop()
							#2.2.2.1 newdex    
							if newdex != '(':
								stack_expr.append(newdex)
							#2.2.2.2 newdex     
							else:
								break
					#2.2.3 index      
					else:
						while True:
							#2.2.3.0 opr  ，     
							if not stack_opr:
								stack_opr.append(index)
								break
							level_index = dicts[index]
							level_opr = dicts[stack_opr[-1]]
							#2.2.3.1 index       opr         ,index   opr 
							if level_index > level_opr:
								stack_opr.append(index)
								break
							#2.2.3.2 index       opr            , opr         expr  ，   index        opr      
							else:
								topdex = stack_opr.pop()
								stack_expr.append(topdex)
		#3. data           ， opr     ，        expr 
		while True:
			if len(stack_opr)!=0:
				dex = stack_opr.pop()
				stack_expr.append(dex)
			else:
				break
		return stack_expr

(二).逆ポーランド式の計算は、接尾辞式を逆ポーランド式に変換することに比べて、逆ポーランド式の計算は簡単です.以下のステップでいいです.

         stack_res(   List  ),              

          ：

1、      ，  stack_res;
2、       ，  stack_res                      ，     stack_res   
3、          ，    ；

コード実装

def compute(data):

	stack_res = list()
	
	global pat
	
	for index in data:
		#1   ， res 
		if index not in  pat:
			stack_res.append(index)
		#2    
		else:
			# 2.1      
			right_ops = stack_res.pop()
			left_ops = stack_res.pop()
			
			if index == '*':
				res = left_ops*right_ops
				stack_res.append(res)
				
			 #      ，         	
			if index == '/':
				res = left_ops/right_ops
				if right_ops == 0:
					raise Exception('Zero')
				stack_res.append(res)
				
			if index == '+':
				res = left_ops+right_ops
				stack_res.append(res)
				
			if index == '-':
				res = left_ops-right_ops
				stack_res.append(res)
				
	if len(stack_res) == 1:
		return stack_res[0]