C++コード:接尾辞式逆ポーランド式

1.概要
たとえば式「(51+(31+6)*5)*(6+1)」の値を計算すると、どうやって手に入れますか?まず、これは、データ構造の「ツリーの中順遍歴順序」に似た中順表現です.この式は簡単で、この式が先に(31+6)計算され、その後(31+6)*5が計算されることをよく知ることができると考えられているが、コンピュータにとっては、中順序式は複雑な構造であるため、これは困難である.コンピュータは、この式の接尾辞式の値を明確に計算することができ、この接尾辞式は「51 31 6+5*+6 1+*」であり、コンピュータは逆ポーランド式で値を求める方法でこの接尾辞式を計算することができる.接尾辞式は、データ構造の「ツリーの後順ループ順序」に似ています.本質的に中序式は後序式の表現の意味と同じで、中序の形式は人に適して、後序の形式はコンピュータに適しています.では、問題の鍵はどのようにして中序式を後序式に変換するかです.その基本的な考え方は以下に述べる.
1)式の数値については、中間式と後続式の順序は変更されません.中系列式「(51+(31+6)*5)*(6+1)」および後系列式「51 31+5*+6 1+*」のような数字順は、いずれも51 31,6,5,6 1である.
2)中順序式の優先度.カッコの優先度は、加算減算演算子より高い.ネストされた1級かっこの優先度はネストされた2級かっこの優先度より小さい.同じカッコの乗算の優先度は、加算の優先度よりも高くなります.
3)中系列式には括弧がネストされているが,後系列式には括弧がなく,後系列式の生成は各数値の後に演算子を挿入するか挿入しないかのいずれかと理解できる.演算子のデータ構造はスタックの構造を採用し、スタックに格納される要素は【演算子、優先度】である.各数値の後に演算子を挿入するか挿入しないかは、現在の演算子優先度とスタックトップの演算子優先度によって決まります.
 
2.コード

//            
//  ：1）    。2）                
//                 ，                        
//                  
string transToRPN(string s){
	string ans;//              
	//         [  ，   ]；         10，       2，       1，    
	stack> op_stack;
	//     
	stack brackets;
	//           、  、   
	int n = s.length();
	for(int i=0;i='0'&&s[i]<='9'){
			while(s[i]>='0'&&s[i]<='9'){
				ans.push_back(s[i]);
				i++;
			}
			ans.push_back(' ');
			i--;
		}
		
		//                
		if(s[i]=='+'||s[i]=='-'){
			//         
			int current_priority = brackets.size()*10+1; 
			pair p({s[i],current_priority});
			if(op_stack.empty()){//        ，    e1 op e2 ==> e1 e2 op
				op_stack.push(p);
			}else{
				//            
				pair last_node = op_stack.top();
				if(current_priority > last_node.second){
					//  E1 op1 E2 op2 E3,  op2      op1 ==> E1 E2 E3 op2 op1
					//  E2 E3     ，op1         
					op_stack.push(p); 
				}else{
					//  E1 op1 E2 op2 E3,  op2<=op1 ==> E1 E2 op1 E3 op2
					//                           
					while(!op_stack.empty()&&current_priority<=op_stack.top().second){
						ans.push_back(op_stack.top().first);
						ans.push_back(' '); 
						op_stack.pop(); 
					}
					//         ，      
					op_stack.push(p);  
				} 
			}
		}else if(s[i]=='*'||s[i]=='/'){
			//         
			int current_priority = brackets.size()*10+2;
			pair p({s[i],current_priority});
			if(op_stack.empty()){//        ，    e1 op e2 ==> e1 e2 op
				op_stack.push(p);
			}else{
				//            
				pair last_node = op_stack.top();
				if(current_priority > last_node.second){
					//  E1 op1 E2 op2 E3,  op2      op1 ==> E1 E2 E3 op2 op1
					//  E2 E3     ，op1         
					op_stack.push(p); 
				}else{
					//  E1 op1 E2 op2 E3,  op2<=op1 ==> E1 E2 op1 E3 op2
					//                           
					while(!op_stack.empty()&&current_priority<=op_stack.top().second){
						ans.push_back(op_stack.top().first);
						ans.push_back(' '); 
						op_stack.pop(); 
					}
					//         ，      
					op_stack.push(p);  
				} 
			}
			
		}else if(s[i]=='('){//         
			brackets.push(s[i]); 
		}else if(s[i]==')'){//        
			brackets.pop();
		}
	}	
	
	while(!op_stack.empty()){
		pair p = op_stack.top();
		ans.push_back(p.first);
		ans.push_back(' '); 
		op_stack.pop();
	} 
	
	return ans;	
}

アルゴリズム時間複雑度O(n),空間複雑度O(n)