The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

Reverse Polish Notation——标程

 

//Copyright by abilitytao

//All right not reserved!!

 

 

#include <process.h>

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <math.h>

#include <stack>

#include <cstring>

#include <ctype.h>

using namespace std;

 

struct formula

{

       char numormark[100];

};

 

///////////////////////////////////////////////////////////

/////////////////////定义problem类/////////////////////////

///////////////////////////////////////////////////////////

 

class Aeasyproblem

{

private:

       int formulalen;

       char temp[1000];

       formula in[1000];

       formula pos[1000];

public:

       void inputtheformula();

       void intoin();//用于将中缀表达式放入结构体数组，从而实现数字与运算符的分离；

       void intopos();//用于将中缀表达式转化成后缀表达式；

       void showthepos();

};

 

void Aeasyproblem::inputtheformula()

{

       cin>>temp;

}

void Aeasyproblem::intoin()//这是用于解析输入的字符串的函数，将算式中的每个个体存入自己声明的结构体中；

{

       formulalen=0;

       int templen;

       int temlen;

       char tem[100];

 

      

       templen=strlen(temp);

       int i;

       int j;

       j=0;

       for(i=0;i<templen;i+=temlen)

       {

              if(isdigit(temp[i]))

              {

                     sscanf(&temp[i],"%[^-^+^*^/^(^)]",tem);

                     temlen=strlen(tem);

                     strcpy(in[j].numormark,tem);

                     formulalen++;

                     j++;

              }

              else

              {

                     temlen=1;

                     in[j].numormark[0]=temp[i];

                     in[j].numormark[1]='\0';

                     formulalen++;

                     j++;

              }

       }

}

 

 

 

 

void Aeasyproblem::intopos()//这是用于将中缀表达式转化成后缀表达式的函数

{

       /////////////////'(' ')''+''-''*''/''='

       static int isp[7]={ 0,19,12,12,13,13,0};

       static int icp[7]={20,19,12,12,13,13,0};

       int precedence_sta;

       int precedence_token;

 

       stack<formula>sta;

       int i;

       int j;

       char token[100];

       formula start;

       strcpy(start.numormark,"\0");

       sta.push(start);

       j=0;

       for(i=0;i<formulalen;i++)

       {

             

              strcpy(token,in[i].numormark);

              if(strcmp(token,"\0")==0)

                     break;

              if(isdigit(token[0]))

              {

                     strcpy(pos[j].numormark,token);

                     j++;

              }

              else if(strcmp(token,")")==0)

              {

                     while(strcmp(sta.top().numormark ,"(")!=0)

                     {

                            strcpy(pos[j].numormark,sta.top().numormark);

                            j++;

                            sta.pop();

                     }

                     sta.pop();

              }

              else

              {

                            if(strcmp(sta.top().numormark,"(")==0)

                                   precedence_sta=0;

                            if(strcmp(sta.top().numormark,")")==0)

                                   precedence_sta=19;

                            if(strcmp(sta.top().numormark,"+")==0)

                                   precedence_sta=12;

                            if(strcmp(sta.top().numormark,"-")==0)

                                   precedence_sta=12;

                            if(strcmp(sta.top().numormark,"*")==0)

                                   precedence_sta=13;

                            if(strcmp(sta.top().numormark,"/")==0)

                                   precedence_sta=13;

                            if(strcmp(sta.top().numormark,"\0")==0)

                                   precedence_sta=0;

                            if(strcmp(token,"(")==0)

                                   precedence_token=20;

                            if(strcmp(token,")")==0)

                                   precedence_token=19;

                            if(strcmp(token,"+")==0)

                                   precedence_token=12;

                            if(strcmp(token,"-")==0)

                                   precedence_token=12;

                            if(strcmp(token,"*")==0)

                                   precedence_token=13;

                            if(strcmp(token,"/")==0)

                                   precedence_token=13;

                            if(strcmp(token,"\0")==0)

                                   precedence_token=0;

                     while(precedence_sta>=precedence_token)

                     {

                                   pos[j]=sta.top();

                                   j++;

                                   sta.pop();

                            if(strcmp(sta.top().numormark,"(")==0)

                                   precedence_sta=0;

                            if(strcmp(sta.top().numormark,")")==0)

                                   precedence_sta=19;

                            if(strcmp(sta.top().numormark,"+")==0)

                                   precedence_sta=12;

                            if(strcmp(sta.top().numormark,"-")==0)

                                   precedence_sta=12;

                            if(strcmp(sta.top().numormark,"*")==0)

                                   precedence_sta=13;

                            if(strcmp(sta.top().numormark,"/")==0)

                                   precedence_sta=13;

                            if(strcmp(sta.top().numormark,"\0")==0)

                                   precedence_sta=0;

                            if(strcmp(token,"(")==0)

                                   precedence_token=20;

                            if(strcmp(token,")")==0)

                                   precedence_token=19;

                            if(strcmp(token,"+")==0)

                                   precedence_token=12;

                            if(strcmp(token,"-")==0)

                                   precedence_token=12;

                            if(strcmp(token,"*")==0)

                                   precedence_token=13;

                            if(strcmp(token,"/")==0)

                                   precedence_token=13;

                            if(strcmp(token,"\0")==0)

                                   precedence_token=0;

                     }

                     strcpy(start.numormark,token);

                    

                            sta.push(start);

              }

       }

       while(strcpy(token,sta.top().numormark))

 

       {

              if(strcmp(token,"\0")==0)

                     break;

              pos[j]=sta.top();

              j++;

              sta.pop();

       }

       strcpy(pos[j].numormark,"\0");

 

}

 

void Aeasyproblem::showthepos()

{

       int i;

       for(i=0;strcmp(pos[i].numormark,"\0")!=0;i++)

       {

             

              cout<<pos[i].numormark<<' ';

 

       }

       cout<<'\b'<<endl<<endl;

      

}

///////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////Problem类定义完成/////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////////

 

 

 

int main ()

{

       Aeasyproblem justforfun;

       while(1)

       {

              justforfun.inputtheformula();

              justforfun.intoin();

              justforfun.intopos();

              justforfun.showthepos();

       }

       return 0;

}

posted on 2009-02-19 13:05 abilitytao 阅读(763) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理