目前自己测试的表达式都没有出过问题
思路是这样，先将后缀表达式的计算顺序搞出来。。当完全缩出来一个数的时候，如果后面还有要计算的，我们就把它放到后缀表达式的后面
先算后面的。。不断迭代。。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; char sign[]={'+','-','*','/','^','(',')'},opSt[1000007],s[1000007]; ll numSt[1000007]; int opTail,numTail; bool is_sign(char x){ int i; for(i=0;i<7;++i) if(x==sign[i]) return true;return false; } ll calc(ll a,ll b,char x){ int i; for(i=0;i<5;++i){ if(x==sign[i]){ if(x=='+'){ return a+b; } else if(x=='-'){ return a-b; } else if(x=='*'){ return a*b; } else if(x=='/'){ return a/b;//这里是下取整，小心除以0 //除法的顺序 } else if(x=='^'){ return a^b; } } } printf("unknown-op->err! ");//很关键 } void printStack(){ printf("numStack:: "); for(int i=numTail-1;i>=0;--i) printf("%I64d ",numSt[i]); if(!numTail) printf("empty "); printf("opStack:: "); for(int i=opTail-1;i>=0;--i) printf("%c ",opSt[i]); if(!opTail) printf("empty "); } int prev_q[1000007],back_q[1000007],pt,bt,seg_cnt,temp[1000007],tmp_cnt; bool is_res[1000007],is_char[1000007],IS_CHAR[1000007],TMP_CHAR[1000007]; int ans[1000007],cnt; char str[1000007];int Next[1000007],Prev[1000007]; void printBackStr(){ printf("BackStr:: "); for(int i=pt-1;i>=0;--i) printf("%d ",prev_q[i]); printf("===== "); for(int i=0;i<bt;++i) { if(is_char[i]) printf("%c ",back_q[i]); else printf("%d ",back_q[i]); } } void printAns(){ int i; printf("AnsStr:: cnt::%d ",cnt); for(i=0;i<cnt;++i) { if(IS_CHAR[i]) printf("%c",ans[i]); else printf("%d",ans[i]); } printf("| "); } void init(){ opTail=0,numTail=0; pt=0;bt=0;cnt=0;seg_cnt=0; memset(is_res,0,sizeof(is_res)); memset(is_char,0,sizeof(is_char)); memset(IS_CHAR,0,sizeof(IS_CHAR)); memset(TMP_CHAR,0,sizeof(TMP_CHAR)); } void pop_Stack(int x){ if(!x) back_q[bt++]=numSt[numTail-1]; while(numTail&&opTail&&opSt[opTail-1]!='('){ if(numTail-2<0) printf("popStack-err! "); if(!is_res[numTail-2]) prev_q[pt++]=numSt[numTail-2]; back_q[bt++]=opSt[opTail-1];is_char[bt-1]=true; is_res[numTail-1]=false;is_res[numTail-2]=false; ll b=numSt[--numTail],a=numSt[--numTail]; a=calc(a,b,opSt[--opTail]); is_res[numTail]=true; numSt[numTail++]=a; } if(numTail==1&&is_res[numTail-1]){ int i; tmp_cnt=0; seg_cnt++; memset(TMP_CHAR,0,sizeof(TMP_CHAR)); for(i=0;i<cnt;++i) { temp[tmp_cnt++]=ans[i]; if(IS_CHAR[i]) TMP_CHAR[tmp_cnt-1]=1; } memset(IS_CHAR,0,sizeof(IS_CHAR)); cnt=0; for(i=pt-1;i>=0;--i) ans[cnt++]=prev_q[i]; for(i=0;i<bt;++i){ ans[cnt++]=back_q[i]; if(is_char[i]) IS_CHAR[cnt-1]=true; } if(seg_cnt>=2){ if(is_char[bt-1]){ cnt--;IS_CHAR[cnt]=0;//这里忘记修改IS_CHAR，可能输出了退格字符！！ for(i=0;i<tmp_cnt;++i) { ans[cnt++]=temp[i]; if(TMP_CHAR[i]) IS_CHAR[cnt-1]=true; } ans[cnt++]=back_q[bt-1];IS_CHAR[cnt-1]=true; } else{ printf("segment->Exception "); for(i=0;i<tmp_cnt;++i) { ans[cnt++]=temp[i]; if(TMP_CHAR[i]) IS_CHAR[cnt-1]=true; } } } //清空队列 pt=0;bt=0; memset(is_char,0,sizeof(is_char)); } } int main(){ while(~scanf("%s",s)){ int len=strlen(s); int i,j; init(); for(i=0;i<len;++i){ if(is_sign(s[i])){ opSt[opTail++]=s[i]; } else{ ll base=0;int prev_pos=i; while(i<len&&!is_sign(s[i])){ base=base*10+(s[i]-'0'); i++; } i--; numSt[numTail++]=base; if(i==len-1||s[i+1]=='+'||s[i+1]=='-'||s[i+1]=='^'||s[i+1]==')'){ if(i+1<len&&s[i+1]==')'){ //右边是右括号的情况 pop_Stack(0); if(opTail&&opSt[opTail-1]=='(') --opTail; if(i+2==len||i+2<len&&s[i+2]!='*'&&s[i+2]!='/'){//少了最后是括号的判断 pop_Stack(1); } i++;//去除右括号 } else { if(prev_pos>0&&s[prev_pos-1]!='('){ if(i==len-1){ pop_Stack(0); } else if(s[i+1]=='^'){ pop_Stack(0); } else if(s[i+1]=='+'||s[i+1]=='-'){ if(s[prev_pos-1]!='^'){ pop_Stack(0); } } else { printf("JUDGE ERR! "); } } } } } } printf("NORMAL_ANS::%I64d ",numSt[0]); int slen=0; //这里按所有数字不超过10考虑 for(i=0;i<cnt;++i){ if(IS_CHAR[i]) str[slen++]=ans[i]; else str[slen++]=ans[i]+'0'; } numTail=0,opTail=0; for(i=0;i<slen;++i){ Next[i]=i+1; Prev[i]=i-1; } Next[slen-1]=-1; //将str写成了s,命名混淆 for(j=0;j!=-1;j=Next[j]){ if(!is_sign(str[j])){ int t=str[j]-'0'; printf("%d ",t); } else{ printf("%c ",str[j]); } } printf(" "); //在这里char类型自然溢出了。。如果结果太大的话 for(i=0;i!=-1;i=Next[i]){ if(is_sign(str[i])){ ll b=str[Prev[i]]-'0'; ll a=str[Prev[Prev[i]]]-'0'; a=calc(a,b,str[i]); int NextPos=Next[i]; str[Prev[Prev[i]]]=a+'0'; Next[Prev[Prev[i]]]=NextPos; if(NextPos!=-1) Prev[NextPos]=Prev[Prev[i]]; // printf("a::%I64d b:%I64d Next:%d ",a,b,NextPos); for(j=0;j!=-1;j=Next[j]){ if(j==0&&Next[j]==-1) {printf("%I64d",numSt[0]);continue;} if(!is_sign(str[j])){ ll t=str[j]-'0'; printf("%I64d ",t); } else{ printf("%c ",str[j]); } } printf(" "); } } printf("%I64d ",numSt[0]); } return 0; }