transform.cpp

该程序解决了数据结构中的表达式求值问题

#include "stdlib.h"
#include "sqstack.h"
#include "sqstackdouble.h"
#include "string.h"

int precede(char a,char b)
{if(b=='#'||b=='(')return 1;
 if (a=='^')return 1;
 if ((a=='*'||a=='/')&&(b=='-'||b=='+'))return 1;
 if ((a=='*'||a=='/')&&(b=='*'||b=='/'))return 1;
 if ((a=='+'||a=='-')&&(b=='-'||b=='+'))return 1;
 return 0;
 }
bool OpMember(char ch)
{
	if (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'||ch=='#'||ch=='('||ch==')')
		return true;
	else return false;
}
double Operate(double a, char ch,double  b)
{switch(ch)
	{case '+':   return(a+b);
	 case '-':   return(a-b);
	 case '*':   return(a*b);
	 case '/':   if (b == 0){ cerr << "divide by 0!" << endl;exit(0);}
		         return(a/b);
}
}
double evaluation( char suffix[] ){
      // 本函数返回由后缀式suffix表示的表达式的运算结果
	dSqStack S;double b,a;
	double result;
     char ch = *suffix++;  InitStack(S);      // 设置空栈S
      while ( ch != '#' ) {
        if (!OpMember(ch))  Push(S, ch );  // 非"运算符"入操作数栈
        else {
           Pop(S, b);  Pop(S, a);          // 退出栈顶两个操作数
           cout<<a<<ch<<b<<endl;
		   Push(S, Operate(a, ch, b));     // 作相应运算，并将运算结果入栈
        }
        ch= *suffix++;                     // 继续取下一字符
      }
      Pop(S,result);
      return result;
} // evalution


void transform(char Suffix[], char exp[] ) {
      // 从合法的表达式字符串exp求得其相应的后缀式字符串suffix，precede(a,b)
      // 判别算符法的优先程度，当a的优先数≥b 的优先数时，返回 1，否则返回0
    SqStack S;char ch,c;
	int k;char *p;
	InitStack(S);  Push(S, '#');                   // 预设运算符栈的栈底元素为'#'
      p = exp;  ch = *p;  k=0;
      while (!StackEmpty(S)) {
        if (!OpMember(ch)) Suffix[k++] = ch;       // 操作数直接发送给后缀式
        else {
         switch (ch) {
           case '(' : Push(S, ch); break;            // 左括弧一律入栈
		   case  ')': { Pop(S, c);
             while (c!= '(' )            // 自栈顶至左括弧之前的运算符发送给后缀式
             { Suffix[k++] = c;  Pop(S, c) ;}
             break; 
            }
           default : {
             while( GetTop(S, c) && ( precede(c,ch)) ) {              
               Suffix[k++] =c;  Pop(S, c); 
              }  // 将栈中所有优先数不小于当前运算符优先数的运算符发送给后缀式
             if ( ch!= '#' )  Push( S, ch);           // 优先数大于栈顶的运算符入栈
             break;
           } // default 
         } // switch
        } // else
        if ( ch!= '#' ) ch = *++p;  
       } // while 
       Suffix[k] = '\0' ;                             // 添加字符串的结束符
} // transform
void main()
{char a[30]="3+2*4-5#";//这里的3，2，4，5作为数值时候将使用其ascI值
char b[30] ;int n;
transform(b,a);
cout<<a<<endl;
cout<<b<<endl;
cout<<evaluation(b);
}