逆波兰计算器 -- 改头换面中-- 编程爱好者博客

#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#define DATA 0#define SIG 1#define KUOHAO 2using namespace std;struct DataChain{ float data; //////////////数据 char sig; ///////////////符号 int dsflag; /////////////////符号、数据表示符 DataChain *next; ////////////////下推指针 DataChain *pre; //////////////回溯指针}; /////////////////数据链数据结构 struct DataStack /////////////////逆波兰表达式队列{ float data; char sig; bool dsflag; DataStack *next;}; struct tmpSigStack //////////////////逆波兰暂存符号栈{ char sig; tmpSigStack *next; int level; /////////////符号优先级}; struct PolanStack ////////////////////逆波兰队列分析栈{ float data; PolanStack *next;}; DataChain* GetDatafromstr(char *sumData); /////////创建数据链bool CheckData(DataChain *dataHead); //////////检测数据是否合法DataStack* CreatePolanStack(DataChain *dataHead); /////////////////生成逆波兰队列float Calculate(DataStack *dsHead); /////////////由逆波兰队列求得答案 char sumData[1000];void main(){ DataChain *dataHead; /////////////数据链头指针 DataStack *dsHead,*tmpdsHead; int pos=0; float dest; cin>>sumData; dataHead=GetDatafromstr(sumData); if (dataHead==NULL) { cout<<"fuck"<<endl; exit(1); } if (!CheckData(dataHead)) { cout<<"shit"<<endl; exit(1); } dsHead=CreatePolanStack(dataHead); tmpdsHead=dsHead; while(tmpdsHead->next!=NULL) { tmpdsHead=tmpdsHead->next; if (tmpdsHead->dsflag==DATA) cout<<tmpdsHead->data<<" "; else cout<<tmpdsHead->sig<<" "; } dest=Calculate(dsHead); cout<<dest;}////////////////////////////////////////////////////////////////////////////////////////////////////////////从输入字符串获取数据DataChain* GetDatafromstr(char *sumData) { char tmpData[100]; char tmp; DataChain *tmpHead; DataChain *tmpChain; DataChain *prePos; float getData; int postmp=0; int pos=0; bool pointFlag=0; //////////////////小数点标记 tmp=sumData[0]; tmpHead=new DataChain; tmpHead->next=NULL; tmpHead->pre=NULL; prePos=tmpHead; while(true) { if (tmp=='\0') { if (postmp==0) break; else { tmpData[postmp]='\0'; if (tmpData[0]=='.'||tmpData[postmp-1]=='.') ////////// return NULL; //////////////////////////数据非法处理 getData=(float)atof(tmpData); //////// tmpChain=new DataChain; ////数据加入数据链 tmpChain->data=getData; ////// tmpChain->pre=prePos; // tmpChain->next=NULL; /// prePos->next=tmpChain; //// prePos=tmpChain; /// tmpChain->dsflag=DATA; /////////////////// } break; } if (tmp>='0'&&tmp<='9') ///////////////////数字处理 { tmpData[postmp]=tmp; postmp++; } if (tmp=='.') ////////////小数点处理 { if (pointFlag==0) { tmpData[postmp]=tmp; postmp++; pointFlag=1; } else return NULL; } ////////////////////////////符号处理 if (tmp=='('||tmp==')'||tmp=='+'||tmp=='-'||tmp=='*'||tmp=='/') { if (postmp) { tmpData[postmp]='\0'; if (tmpData[0]=='.'||tmpData[postmp-1]=='.') ////////// { cout<<"Eleagle input"<<endl; return NULL; } /////////////////////////数据非法处理 getData=(float)atof(tmpData); /// tmpChain=new DataChain; /// tmpChain->data=getData; /// tmpChain->pre=prePos; /// tmpChain->next=NULL; /// prePos->next=tmpChain; //// prePos=tmpChain; ////数据加入数据链 tmpChain->dsflag=DATA; ////// memset(tmpData,0,sizeof(tmpData)); ///// } tmpChain=new DataChain; ///// tmpChain->sig=tmp; ////// tmpChain->pre=prePos; //////// tmpChain->next=NULL; ///////// prePos->next=tmpChain; /// prePos=tmpChain; ////// if (tmpChain->sig=='('||tmpChain->sig==')') tmpChain->dsflag=KUOHAO; ///////符号加入数据链 else tmpChain->dsflag=SIG; postmp=0; pointFlag=0; } pos++; tmp=sumData[pos]; } return tmpHead;}///////////////////////////////////////////////////////////////////////////////////////////////数据检测bool CheckData(DataChain *dataHead){ int num=0; DataChain *tmpChain; tmpChain=dataHead; while (tmpChain->next!=NULL) { tmpChain=tmpChain->next; if (tmpChain->dsflag==KUOHAO&&tmpChain->sig=='(') /////////括号匹配处理 num++; if (tmpChain->dsflag==KUOHAO&&tmpChain->sig=='(') ////////括号匹配 { num--; if (num<0) { cout<<"Eleagle input!"<<endl; //////////////反括号多余正括号，非法 return false; } } if (tmpChain->next!=NULL) { if (tmpChain->dsflag==tmpChain->next->dsflag&&tmpChain-> dsflag!=KUOHAO) ///////////数据重合与算符重合处理 return false; if (tmpChain->dsflag==DATA&&tmpChain->next->sig=='(') ///////////////////数据与左括号处理 return false; if (tmpChain->sig==')'&&tmpChain->next->sig=='(') ////////////////左括号与右括号重合处理 return false; if (tmpChain->sig=='('&&tmpChain->next->sig==')') return false; } } if (dataHead->next->dsflag==SIG||tmpChain->dsflag==SIG) return false; return true;}//////////////////////////////////////////////////////////////////////////////构造逆波兰表达式DataStack* CreatePolanStack(DataChain *dataHead){ tmpSigStack *tSigStack; /////////////头指针 tmpSigStack *tmpsigStack; DataStack *dataStackhead; DataStack *tmpdatastack; DataStack *dsnowPos; DataChain *tmpDataHead; DataChain *deltmp; int bracket=0; ////////////////括号层数 tmpDataHead=dataHead; tSigStack=new tmpSigStack; // tSigStack->next=NULL; // tSigStack->level=0; ////// dataStackhead=new DataStack; ///栈初始化 dataStackhead->next=NULL; ///////////////// dsnowPos=dataStackhead; /////////// //////////////////////////////分析构造逆波兰队列 while(tmpDataHead->next!=NULL) { deltmp=tmpDataHead; tmpDataHead=tmpDataHead->next; if (tmpDataHead->dsflag==DATA) { tmpdatastack=new DataStack; tmpdatastack->data=tmpDataHead->data; tmpdatastack->dsflag=DATA; tmpdatastack->next=NULL; dsnowPos->next=tmpdatastack; dsnowPos=tmpdatastack; delete deltmp; continue; } ///////////////////////数据进入队列 if (tmpDataHead->dsflag==KUOHAO&&tmpDataHead->sig=='(') { bracket++; delete deltmp; continue; } /////////////////////////括号层级处理 if (tmpDataHead->dsflag==KUOHAO&&tmpDataHead->sig==')') { bracket--; delete deltmp; continue; } ///////////////////////括号层级处理 if (tmpDataHead->dsflag==SIG) { int Priority; if (tmpDataHead->sig=='+'||tmpDataHead->sig=='-') Priority=1+bracket*10; if (tmpDataHead->sig=='*'||tmpDataHead->sig=='/') Priority=3+bracket*10; { while(true) { if (tSigStack->next!=NULL) { if (Priority<=tSigStack->next->level) ////////////若前一算符优先级大于或等于当前运算符，前运算符出栈 { tmpdatastack=new DataStack; tmpdatastack->sig=tSigStack->next->sig; /////////取栈顶元素 tmpdatastack->dsflag=SIG; tmpdatastack->next=NULL; dsnowPos->next=tmpdatastack; dsnowPos=tmpdatastack; //////////////////////将前一运算符加入队列 tmpSigStack *delStack; delStack=tSigStack->next; tSigStack->next=tSigStack->next->next; delete delStack; ////////////////////////删除符号栈顶元素 } else break; } else break; } } tmpsigStack=new tmpSigStack; tmpsigStack->level=Priority; tmpsigStack->sig=tmpDataHead->sig; ////////////////将当前符号加入栈顶 tmpsigStack->next=tSigStack->next; /////////////// tSigStack->next=tmpsigStack; ////////////////// } ////////////////////////////运算符队列处理 delete deltmp; } tmpsigStack=tSigStack; while(tmpsigStack->next!=NULL) { tmpSigStack *delStack; delStack=tmpsigStack; tmpsigStack=tmpsigStack->next; tmpdatastack=new DataStack; tmpdatastack->sig=tmpsigStack->sig; /////////取栈顶元素 tmpdatastack->next=NULL; dsnowPos->next=tmpdatastack; dsnowPos=tmpdatastack; delete delStack; } return dataStackhead;} float Calculate(DataStack *dsHead){ DataStack* tmpdsHead; PolanStack* psHead; PolanStack* tmpPStack; tmpdsHead=dsHead; psHead=new PolanStack; psHead->next=NULL; while(tmpdsHead->next!=NULL) { tmpdsHead=tmpdsHead->next; if (tmpdsHead->dsflag==DATA) { tmpPStack=new PolanStack; tmpPStack->data=tmpdsHead->data; tmpPStack->next=psHead->next; psHead->next=tmpPStack; } else { float dest=0; PolanStack *delDS; switch (tmpdsHead->sig) { case '+': dest=psHead->next->data+psHead->next->next->data; psHead->next->next->data=dest; delDS=psHead->next; psHead->next=psHead->next->next; delete delDS; break; case '-': dest=psHead->next->next->data-psHead->next->data; psHead->next->next->data=dest; delDS=psHead->next; psHead->next=psHead->next->next; delete delDS; break; case '*': dest=psHead->next->data*psHead->next->next->data; psHead->next->next->data=dest; delDS=psHead->next; psHead->next=psHead->next->next; delete delDS; ///////////////////////////////递进计算 break; case '/': dest=psHead->next->next->data/psHead->next->data; psHead->next->next->data=dest; delDS=psHead->next; psHead->next=psHead->next->next; delete delDS; break; } } } return psHead->next->data;}

博客介绍

正文

逆波兰计算器2009-07-08 21:57:00

评论