C++实现数据结构（源代码）

// test formula based stack class #include <iostream.h> #include "stack1.h" #include "power.h" #include <ctype.h> void ComExp(char *Exp) // caculate the value for Exp expression { stack<char> s2 (100); // set space for the caculated character stack stack<int> s1 (100); // set space for the integer stack int i=0; // register the times of the caculate int s=0; // turn the caculated character to digit value char ch; // register the caculated character int val1, val2, val; while(Exp[i]!='\0'){ // expression is not the end switch(Exp[i]){// deal with the exp[i] // digist case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': s=0; // caculate the digit value do{ s=s*10+Exp[i]-48; i++; } while(isdigit(Exp[i])); s2.Push(s); break; // deal with the '(' case'(': s1.Push('('); i++; break; // deal with the ')' case')': ch=s1.Pop(); while(ch!='('){ // caculated object pop of the stack val1=s2.Pop(); val2=s2.Pop(); switch(ch){ case '+': val=val1+val2; s2.Push(val); break; case '-': val=val2-val1; s2.Push(val); break; case '*': val=val1+val2; s2.Push(val); break; case '/': val=val2/val1; s2.Push(val); break; case '^': val=Power(val2, val1); s2.Push(val); break; } ch=s1.Pop(); } i++; break; // deal with the '+''-' case '+': case '-': if(!s1.IsEmpty()){ ch=s1.GetTop(); while(ch!='('){ ch=s1.Pop(); val1=s2.Pop(); val2=s2.Pop(); switch(ch){ case '+': val=val1+val2; s2.Push(val); break; case '-': val=val2-val1; s2.Push(val); break; case '*': val=val1*val2; s2.Push(val); break; case '/': val=val2/val1; s2.Push(val); break; case '^': val=Power(val2, val1); s2.Push(val); break; } if(!s1.IsEmpty()) ch=s1.GetTop(); else break; } } s1.Push(Exp[i]); i++; break; // deal with '*''/' case '/': case '*': if(!s1.IsEmpty()){ ch=s1.GetTop(); if((ch=='*') || (ch=='/')){ ch=s1.Pop(); val1=s2.Pop(); val2=s2.Pop(); switch(ch){ case '*': val=val1*val2; s2.Push(val); break; case '/': val=val2/val1; s2.Push(val); break; case '^': val=Power(val2, val1); s2.Push(val); break; } } } s1.Push(Exp[i]); i++; break; // deal with '^' case '^': if(!s1.IsEmpty()){ ch=s1.GetTop(); if(ch=='^'){ ch=s1.Pop(); val1=s2.Pop(); val2=s2.Pop(); switch(ch){ case '^': val=Power(val2, val1); s2.Push(val); break; } } } s1.Push(Exp[i]); i++; break; } // switch the Exp[i] is end }// while the exp[i] is end // when the data in () is finished while(!s1.IsEmpty()){ ch=s1.Pop(); val1=s2.Pop(); val2=s2.Pop(); switch(ch){ case '+': val=val1+val2; s2.Push(val); break; case '-': val=val2-val1; s2.Push(val); break; case '*': val=val1*val2; s2.Push(val); break; case '/': val=val2/val1; s2.Push(val); break; case '^': val=Power(val2, val1); s2.Push(val); break; } } // output the result cout<<Exp<<" = "; cout<<val<<endl; } int main() { char Exp[20]="3+12^3-4*6/9\0 "; // end with white space ComExp(Exp); return 0; }