数据结构中栈的应用——中缀表达式的计算

/  /**基本思想     如果当前字符为数字 ：则对其进行数字化（减去一个‘0’），然后将其压入数栈。    如果当前字符为‘（’：则直接压入符栈。    如果当前字符为‘）’：      则从数栈中去顶部两个数，后一个作为左操作数进行计算，根据符栈中的操作符进行计算          并将结果重新压入数栈，循环此操作直至符栈顶端元素为‘（’，再将‘（’舍弃，      在这种情况下无须考虑优先级，因为优先级的问题已经被下一种情况解决了。    如果是其他操作符，则要进行优先级的比较：      如果外部操作符的优先级 大于 符栈的当前操作符的优先级 或者 符栈为空，则操作符直接入栈      否则        当外部操作符的优先级 小于 符栈的当前操作符的优先级        从栈中取两个操作数，后一个作为作操作数，        根据符栈中的操作符进行计算并将结果重新保存到数栈中        循环结束，还要将外部操作符入栈。    最后根据符栈中的符号进行计算直到操作符栈为空，返回数栈的栈顶元素，也就是计算结果。*/ // 源代码 // Stack.cpp const   int  SIZE = 100 ; // 定义栈模板类 template  < class  T > class  Stack ... {T data[SIZE];int top;public:Stack()...{top=-1;};~Stack()...{}bool isEmpty()...{if(top==-1)return 1;return 0;}void Push(T x);T Pop();T GetTop();void Print();} ; // 栈模板类的实现 template  < class  T > void  Stack < T > ::Push(T x) ... {if(top==100)throw"上溢";data[++top]=x;} template  < class  T > T Stack < T > ::GetTop() ... {return data[top];} template  < class  T > T Stack < T > ::Pop() ... {if(top==-1)throw "下溢";return data[top--];} template  < class  T > void  Stack < T > ::Print() ... {while(top!=-1)   cout<<data[top--];} // main.cpp #include  < iostream > #include  < string > #include  " Stack.cpp " using   namespace  std; int  Rank( char  a) ... {//用于计算优先级if(a=='(')   return 1;else if(a=='+'||a=='-')   return 2;else if(a=='*'||a=='/')   return 3;} Stack < char >  OPTR;Stack < double >  OPND; // 操作符和操作数栈 void  Cal(); // 函数声明 用于计算 double  Calculate( const   string   & s) ... {double result;for(int i=0;i!=s.size();++i)...{   if(s[i]>='0'&&s[i]<='9')...{    OPND.Push(s[i]-'0');   }   else if(s[i]=='(')    OPTR.Push(s[i]);   else if(s[i]==')')   ...{    while(OPTR.GetTop()!='(')     Cal();    OPTR.Pop();   }   else    if(Rank(s[i])>Rank(OPTR.GetTop())||OPTR.isEmpty())    OPTR.Push(s[i]);    else...{     while(Rank(OPTR.GetTop())>=Rank(s[i])      &&!OPTR.isEmpty())      Cal();     OPTR.Push(s[i]);    }}while(!OPTR.isEmpty())   Cal();result = OPND.Pop();return result;}     void  Cal() ... {double temp;switch(OPTR.Pop())...{      case '+':       temp=OPND.Pop();       temp=OPND.Pop()+temp;       OPND.Push(temp);break;      case '-':       temp=OPND.Pop();       temp=OPND.Pop()-temp;       OPND.Push(temp);break;      case '*':       temp=OPND.Pop();       temp=OPND.Pop()*temp;       OPND.Push(temp);break;      case '/':       temp=OPND.Pop();       temp=OPND.Pop()/temp;       OPND.Push(temp);break;     }} int  main() ... {string exp;cin>>exp;cout<<exp<<'='<<Calculate(exp)<<endl;system("pause");return 0;}