スタック実装式の評価

22137 ワード

スタック実装式の評価-逆ポーランド法
データ構造をまともに勉強して1ヶ月以上経ち、基本的な線形テーブルとvector、list、dequeなどが浅く接触しました.実験は学生情報管理の順序表実現とチェーン表実現を行い,両者にはそれぞれメリットとデメリットがある.しかし、データ構造といくつかのアルゴリズムを学ぶことによって、私はそれらのすごい人物と彼らが書いた不思議なアルゴリズムにとても崇拝して、胸の中は熱くて、現実が私を破壊して軽挙妄動する勇気がありません.
これは、データ構造の制限されたテーブルであるスタックに接触したばかりではありません.スタックは先進的な後出(FILO)であり、この特性はこのデータ型に独特の個性を与えている.彼は一端からpush圧入とpopポップアップ操作しかできない.これはちょうど私が式を作って値を求める要求を記号しています.もちろん私は、学んだ以上、深いところを掘って、もっと深いところの人々が作った木と探求を見てみたいと思っています.
一般的に、コンピュータは、a+b*c+(d*e+f)*gのような式を処理し、演算子の優先度に従ってサブ式を前後して計算する必要がある.従って、接尾辞変換接尾辞法(逆ポーランド)を用いて、二義性がなく、順次処理可能な式に変換する.ソース:


  
  
  
  
   
   
   
   //2011-10-10 by bibodeng 
   
   
   
   //          
   
   
   
   //    ：                
   
   
   
   //            
   
   
   
   #include <iostream> 
   
   
   
   #include <stack> 
   
   
   
   #include <vector> 
   
   
   
   #include <string> 
   
   
   
   #include <sstream> 
   
   
   
   using namespace std; 
   
   
   
   typedef vector<string> STRVECTOR; 
   
   
   
   void show_vector( STRVECTOR &v); 
   
   
   
   double str2num(string s); 
   
   
   
   string num2str(double i); 
   
   
   
    
   
   
   
   void main() 
   
   
   
   { 
   
   
   
       //     ，                  
   
   
   
       stack <string,vector<string>> st1 ; 
   
   
   
       vector<string> input;//           vector   
   
   
   
       vector<string> temp;//         
   
   
   
        
   
   
   
       char ans; 
   
   
   
       string a; 
   
   
   
   //******************************************** 
   
   
   
       do 
   
   
   
       { 
   
   
   
           system("cls"); 
   
   
   
           STRVECTOR::iterator ite; 
   
   
   
           cout<<"        "<<endl; 
   
   
   
           int APPY_SIZE; 
   
   
   
           cin>>APPY_SIZE; 
   
   
   
            
   
   
   
           cout<<"           ,            ："<<endl; 
   
   
   
           for( int i=0;i<APPY_SIZE;i++) 
   
   
   
           { 
   
   
   
               cin>>a; 
   
   
   
               input.push_back(a); 
   
   
   
           } 
   
   
   
           cout<<"        ："<<endl; 
   
   
   
           show_vector(input); 
   
   
   
    
   
   
   
           //             0    ，1  , 2    ,     
   
   
   
           int flag=0; 
   
   
   
    
   
   
   
   //*******************          ******************* 
   
   
   
   //***********************    ************************** 
   
   
   
           for(unsigned int i=0;i<input.size();i++) 
   
   
   
           { 
   
   
   
               //  input，            ，     ，    temp 
   
   
   
               //     +   - 
   
   
   
                
   
   
   
    
   
   
   
                //       + - 
   
   
   
                  if("+"==input[i] || "-"==input[i]) 
   
   
   
                   {               
   
   
   
                       //            ，         ( 
   
   
   
                       while(!st1.empty()) 
   
   
   
                       { 
   
   
   
                           if(st1.top()=="(") 
   
   
   
                               break; //   （     ，      ），（     
   
   
   
    
   
   
   
                           temp.push_back(st1.top()); 
   
   
   
                           st1.pop(); 
   
   
   
                           //     
   
   
   
                       } 
   
   
   
                       //      ，  +   -    
   
   
   
                       st1.push(input[i]); 
   
   
   
                   } 
   
   
   
   //************************    *************************** 
   
   
   
   //         + - ，      
   
   
   
    
   
   
   
               else if("*"==input[i] || "/"==input[i]) 
   
   
   
               {    
   
   
   
                           if(!st1.empty())    //   
   
   
   
                           { 
   
   
   
                               //            
   
   
   
                               if(st1.top()=="+"||st1.top()=="-") 
   
   
   
                               st1.push(input[i]); 
   
   
   
                                
   
   
   
                               //     ，       
   
   
   
                               else if(st1.top()=="*"||st1.top()=="/") 
   
   
   
                                   { 
   
   
   
                                       while(!st1.empty()&&st1.top()!="(") 
   
   
   
                                       { 
   
   
   
                                           temp.push_back(st1.top()); 
   
   
   
                                           st1.pop();//   
   
   
   
                                       } 
   
   
   
                                   }    
   
   
   
                               else if(st1.top()=="(") 
   
   
   
                                   st1.push(input[i]); 
   
   
   
                           }    
   
   
   
                           //        ，       
   
   
   
                               if (st1.empty()) 
   
   
   
                                       st1.push(input[i]);      
   
   
   
    
   
   
   
                       } 
   
   
   
   //************************    **************************** 
   
   
   
    
   
   
   
                   //     ,     
   
   
   
                   else if(input[i]== "(") 
   
   
   
                       { 
   
   
   
                           st1.push(input[i]); 
   
   
   
                           flag++;  //    ，        
   
   
   
                       } 
   
   
   
                 //     ，       ，         
   
   
   
                  else if(input[i]== ")") 
   
   
   
                       { 
   
   
   
                           //     （     
   
   
   
                           if(!st1.empty()) 
   
   
   
                           { 
   
   
   
                               while(st1.top()!="(")//        
   
   
   
                               { 
   
   
   
                                   temp.push_back(st1.top()); 
   
   
   
                                   st1.pop(); 
   
   
   
                               } 
   
   
   
                               if(st1.top()=="(") 
   
   
   
                               { 
   
   
   
                                   st1.pop();//     flag 
   
   
   
                                   flag--; 
   
   
   
                               }                    
   
   
   
                           } 
   
   
   
                       } 
   
   
   
   //*********************************       temp************************ 
   
   
   
                   else if(input[i]!="+"&& input[i]!="-"&&input[i]!="*"&&input[i]!="/"&&input[i]!="("&&input[i]!=")") 
   
   
   
                   temp.push_back(input[i]); 
   
   
   
   //************************      ************************* 
   
   
   
           } 
   
   
   
    
   
   
   
    
   
   
   
       //         temp  
   
   
   
       while(!st1.empty()) 
   
   
   
           { 
   
   
   
               temp.push_back(st1.top()); 
   
   
   
               st1.pop(); 
   
   
   
           } 
   
   
   
    
   
   
   
    
   
   
   
       //       
   
   
   
       show_vector(temp); 
   
   
   
   //********************************************************** 
   
   
   
       //        ，        
   
   
   
       stack <string,vector<string>> final; 
   
   
   
       double x=0,y=0; //x,y             
   
   
   
       double result=0; //result          
   
   
   
    
   
   
   
           //        
   
   
   
       for(unsigned int i=0;i<temp.size();i++) 
   
   
   
           { 
   
   
   
               //        
   
   
   
               if(temp[i]!="+"&& temp[i]!="-"&&temp[i]!="*"&&temp[i]!="/"&&temp[i]!="("&&temp[i]!=")") 
   
   
   
                   final.push(temp[i]);//        
   
   
   
    
   
   
   
               else //       ,              ，        
   
   
   
               { 
   
   
   
                   if(!final.empty()) 
   
   
   
                   { 
   
   
   
                       x=str2num(final.top()); 
   
   
   
                       final.pop(); 
   
   
   
                       y=str2num(final.top()); 
   
   
   
                       final.pop(); 
   
   
   
                   } 
   
   
   
    
   
   
   
                       if(temp[i]== "+")result=x+y; 
   
   
   
                       else if(temp[i]== "-")result=y-x; 
   
   
   
                       else if(temp[i]== "*")result=x*y; 
   
   
   
                       else if (temp[i]=="/")result=y/x; 
   
   
   
                                            
   
   
   
                       string temp1; 
   
   
   
                       temp1=num2str(result); 
   
   
   
                        
   
   
   
                       final.push(temp1); 
   
   
   
               } 
   
   
   
    
   
   
   
           } 
   
   
   
       cout<<result<<endl; 
   
   
   
            
   
   
   
   //******************************************************************** 
   
   
   
           cout<<"      (Y/n) "<<endl; 
   
   
   
           cin>>ans; 
   
   
   
           input.clear(); 
   
   
   
           temp.clear(); 
   
   
   
       }while(ans=='y'||ans=='Y'); 
   
   
   
   //******************************************** 
   
   
   
   } 
   
   
   
    
   
   
   
    
   
   
   
    
   
   
   
    
   
   
   
   //  vector   
   
   
   
   void show_vector( STRVECTOR &v) 
   
   
   
   { 
   
   
   
       STRVECTOR::iterator ite; 
   
   
   
       for(ite=v.begin();ite!=v.end();ite++) 
   
   
   
           cout<<*ite; 
   
   
   
       cout<<endl; 
   
   
   
   } 
   
   
   
    
   
   
   
   //       
   
   
   
   double str2num(string s) 
   
   
   
    {   
   
   
   
           double num; 
   
   
   
           stringstream ss(s); 
   
   
   
           ss>>num; 
   
   
   
           return num; 
   
   
   
   } 
   
   
   
   //       
   
   
   
   string num2str(double i) 
   
   
   
   { 
   
   
   
           stringstream ss; 
   
   
   
           ss<<i; 
   
   
   
           return ss.str(); 
   
   
   
   }

最も重要なステップは、接尾辞を接尾辞に変換することです.4つのケースに分けて+-、優先度が最も低い場合は、st 1スタックの演算子を(またはst 1が空になるまでポップアップするだけです.*/などの優先度が高い場合は、いくつかのケースに分けられます.しかし、基本的には3つあります.
1、優先度が低い場合、直接押し込む
2、同じ優先順位のイジェクト後に押し込む
3、突き当たる(直接押し込む.
最後の2つのケース(「(」と「)」)が比較的扱いやすく、(優先度が最も高く、直接押し込まれます.)に遭遇すると、左かっこ「(」との間の演算子が結果にポップアップされ、最後に「(」がポップアップされ、結果には送られません.
コード化の際にかなりの問題が発生し,最後に各種バグを監視で清掃する.コンピュータの中のいくつかの微細な論理は確かに無視できない.すべての文は試練に耐えなければならない.
この式の評価は、コンパイラエンジニアリングの重要な構成部分であり、多くのシンボルバランスや、簡単なif elseなどの多くのマッチング問題に関連していることがわかります.コンパイラは文法の正しいアルゴリズム言語の意味を正確に機械言語に翻訳しなければならない.しかし、この中には、コンパイラの使用者として心配する必要はありませんが、周到な細部を考慮するのは難しい人がたくさんいます.しかし、私たちが使っているアルゴリズム言語の柔軟性から見ると、コンパイラを書く人にポットを飲ませるのに十分です.だから、私は巨大なコンパイラを書くことができる人を心から崇拝しています.stallmanのような天才型ハッカーは、その時になったら必ず彼が書いたgccの中の巧みな天工のコードを見てみなければならない.
最近、データ構造を学ぶことで、現実の多くのものをモデルに描いて実現することができると思います.そして、とても面白いものもあります.例えばスタックで迷路を歩き、循環チェーンテーブルでジョセフリングを解く.これらの問題はすべてとても面白くて、その上この中に良いアルゴリズムが少なくなくて、有名なknuthが書いたジョセフリングアルゴリズムのようで、かなり簡潔で、効率も高くて、普通の人が書いたアルゴリズムは大列で効率が低くて、不幸にも私自身も普通の人です.現実社会では、良いアルゴリズムは往々にして人を奮い立たせ、効率を倍増させることができる.特にこの情報が急速に発展している時代には、アルゴリズムはさらに重要だ.このような大きな演算量を考えてみると、アルゴリズムが良ければ、一度の処理でどれだけの時間と空間を節約したのか.今、アルゴリズムを正式にマスターした時代.
2011-10-11 by bibodeng

プログラミングの方法-文字列の回転

最大公約数最小公倍数