biaodashi.cpp

将中缀表达式转换成后缀表达式后

#include<iostream> 
#include<string> 
#define OK 1 
#define ERROR -1 
#define OVERFLOW -2 
#define DONE 2 
#define MAX 1000 
#define STACK_INIT_SIZE 10 
#define STACKINCREMENT 2 
typedef int Status; 
typedef int SElemType; 
using namespace std; 

typedef struct SqStack 
{ 
    SElemType *base; 
    SElemType *top; 
    int stacksize; 
}SqStack; 

Status InitStack(SqStack *S) 
{ 
    (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); 
    if(!(*S).base) 
        return OVERFLOW; 
    (*S).top=(*S).base; 
    (*S).stacksize=STACK_INIT_SIZE; 
    return OK; 
} 

Status GetTop(SqStack S,SElemType *e) 
{ 
    if(S.top>S.base) 
    { 
        *e=*(S.top-1); 
        return OK; 
    } 
    else 
        return ERROR; 
} 

Status StackPush(SqStack *S,SElemType e) 
{ 
    if((*S).top-(*S).base>=(*S).stacksize) 
    { 
        (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); 
        if(!(*S).base) 
            return OVERFLOW; 
        (*S).top=(*S).base+(*S).stacksize; 
        (*S).stacksize+=STACKINCREMENT; 
    } 
    *((*S).top)++=e; 
    return OK; 
} 

Status StackPop(SqStack *S,SElemType *e) 
{ 
    if((*S).top==(*S).base) 
        return ERROR; 
    *e=*--(*S).top; 
    return OK; 
} 

/*SElemType CmPriority(SElemType t1,SElemType t2) 
{ 
    SElemType f;//1代表t2优先级比t1高，2反之，3相等 
    switch(t1) 
    { 
    case '+': 
    case '-':if(t2=='+'||t2=='-'||t2=='*'||t2=='/'||t2==')')f=2; 
            else f=1; 
            break; 
    case '*': 
    case '/':if(t2=='+'||t2=='-'||t2=='*'||t2=='/'||t2==')'||t2=='#')f=2; 
            else f=1;   
            break; 
    case '(':switch(t2) 
            { 
    case ')':f=3;break; 
    default: f=2; 
            } 
            break; 
    case '#':switch(t2) 
            { 
    case '#':f=3;break; 
    default: f=2; 
            } 
    } 

    return f; 
} 
*/ 
SElemType CmPriority(SElemType t1,SElemType t2) //1代表(1<2) //判断符号的优先级，乘除号优先级高于加 减,右括号优先级高于‘#’(可以理解为‘＝’)，低于其他（除左括号外）符号，左括号高于其他任何符号
{ 
   SElemType f; 
   switch(t2) 
   { 
     case '+': 
    case '-':if(t1=='+'||t1=='-'||t1=='*'||t1=='/'||t1==')')f=2;//2代表1>2,与表3.1相反 
              else f=1; 
              break; 
     case '*': 
     case '/':if(t1=='*'||t1=='/'||t1==')')f=2; 
              else f=1; 
              break; 
     case '(':if(t1==')') 
              { 
                printf("ERROR1\n"); 
                exit(ERROR); 
              } 
              else 
                f=1; 
              break; 
     case ')':switch(t1) 
              { 
                case '(':f=3; 
                         break; 
                case '#':printf("ERROR2\n"); 
                         exit(ERROR); 
                default: f=2; 
              } 
              break; 
    case '#':switch(t1) 
              { 
                case '#':f=3; 
                         break; 
                case '(':printf("ERROR2\n"); 
                         exit(ERROR); 
                default: f=2; 
              } 
   } 
   return f; 
} 

SElemType Evaluate() 
{ 
    SqStack s1,s2; 
    int a,b,d,x,oper,number,num; 
    char c;   
    char e[1000];                            
    int i; 
    InitStack(&s1); 
    StackPush(&s1,'#'); 
    InitStack(&s2); 
    c=getchar(); 
    GetTop(s1,&x); 
    while(c!='#'||x!='#') 
    { 

        if(c>='0'&&c<='9') 
        { 
            i=0; 
            do 
            { 
                e[i]=c; 
                i++; 
                c=getchar(); 
            }while(c>='0'&&c<='9'); 
            e[i]=0; 
            d=atoi(e); 
            StackPush(&s2,d); 
        } 
        else 
        { 
        if(CmPriority(x,c)==1){StackPush(&s1,c);c=getchar();} 
            else if(CmPriority(x,c)==2) 
            {       
                StackPop(&s1,&oper); 
                StackPop(&s2,&b); 
                StackPop(&s2,&a); 
                if(oper=='+')num=a+b; 
                else if(oper=='-')num=a-b; 
                else if(oper=='*')num=a*b; 
                else if(oper=='/'){if(b==0){x=-1;break;} 
                                   else num=a/b;} 
                number=num; 
                StackPush(&s2,number); 
            } 
            else {StackPop(&s1,&x);c=getchar();} 
        } 
            GetTop(s1,&x); 
    } 
    GetTop(s2,&x); 
    return x; 
} 

int main() 
{ 
    int number; 
    cout<<"This Program is used to figure out the formula."<<endl; 
    cout<<"Notice! Press '#' to each of line!!!"<<endl<<endl<<endl; 
    cout<<"Now You can input what you want!"<<endl; 
    /*while(1) */
    { 
        number=Evaluate(); 
        cout<<"The result shows as following..."<<endl; 
        if(number==-1)cout<<"Illegal Input!!!"<<endl; 
        else cout<<number<<endl; 
    } 
    return 0; 
}