北京理工大学数据结构实验2

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：

1从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。

2输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。

例如，输入：4+2*5=                输出：14

      输入：(4+2)*(2-10)=            输出：-48

程序如下：

#include

#include

#include

#define OK  1

#define ERROR  0

#define OVERFLOW  -2

#define STACK_INIT_SIZE  100  //存储空间初始分配量

#define STACKINCREMENT   10  //存储空间分配增量

typedef struct{//定义运算符栈数据类型

    char *base;

    char *top;

    int stacksize;

}SqStack1;

typedef struct{//定义操作数栈数据类型

    int *base;

    int *top;

    int stacksize;

}SqStack2;

int InitStack1(SqStack1 &S){//构造一个空的运算符栈

    S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));

    if(!S.base) exit(OVERFLOW);

    S.top=S.base;

    S.stacksize=STACK_INIT_SIZE;

    return OK;

}//InitStack1

int InitStack2(SqStack2 &S){//构造一个空的操作数栈

    S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));

    if(!S.base) exit(OVERFLOW);

    S.top=S.base;

    S.stacksize=STACK_INIT_SIZE;

    return OK;

}//InitStack2

char GetTop1(SqStack1 S){//若栈不空，则用char型元素e返回S的栈顶元素，并返回OK；否则返回ERROR

    char e;

    if(S.top==S.base) return ERROR;

    e=*(S.top-1);

    return e;

}//GetTop1

int GetTop2(SqStack2 S){//若栈不空，则用int型元素e返回S的栈顶元素，并返回OK；否则返回ERROR

    int e;

    if(S.top==S.base) return ERROR;

    e=*(S.top-1);

    return e;

}//GetTop2

int Push1(SqStack1 &S,char e){//插入char型元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize){

        S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));

        if(!S.base) exit(OVERFLOW);

        S.top=S.base+S.stacksize;

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

    return OK;

}//Push1

int Push2(SqStack2 &S,int e){//插入int型元素e为新的栈顶元素

if(S.top-S.base>=S.stacksize){

        S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));

        if(!S.base) exit(OVERFLOW);

        S.top=S.base+S.stacksize;

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

    return OK;

}//Push2

int Pop1(SqStack1 &S,char &e){//若栈不空，则删除S的栈顶元素，用char型元素e返回其值，并返回OK；否则返回ERROR

    if(S.top==S.base) return ERROR;

    e=*--S.top;

    return OK;

}//Pop1

int Pop2(SqStack2 &S,int &e){//若栈不空，则删除S的栈顶元素，用int型元素e返回其值，并返回OK；否则返回ERROR

    if(S.top==S.base) return ERROR;

    e=*--S.top;

    return OK;

}//Pop2

char Precede(char a,char b){//比较两个相继出现的运算符a和b间的优先级关系

    switch(a){

    case '+':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'<';break;

     case'/':return'<';break;

     case'(':return'<';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'<';break;

        }

    case'-':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'<';break;

     case'/':return'<';break;

     case'(':return'<';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'<';break;

        }

    case'*':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'>';break;

     case'/':return'>';break;

     case'(':return'<';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'<';break;

        }

    case'/':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'>';break;

     case'/':return'>';break;

     case'(':return'<';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'<';break;

        }

    case'^':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'>';break;

     case'/':return'>';break;

     case'(':return'<';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'>';break;

        }

    case'(':

        switch(b){

     case'+':return'<';break;

     case'-':return'<';break;

     case'*':return'<';break;

     case'/':return'<';break;

     case'(':return'<';break;

        case')':return'=';break;

     case'^':return'<';break;

        }

    case')':

        switch(b){

     case'+':return'>';break;

     case'-':return'>';break;

     case'*':return'>';break;

     case'/':return'>';break;

     case')':return'>';break;

     case'=':return'>';break;

     case'^':return'>';break;

        }

    case'#':

        switch(b){

     case'+':return'<';break;

     case'-':return'<';break;

     case'*':return'<';break;

     case'/':return'<';break;

     case'(':return'<';break;

        case'=':return'=';break;

     case'^':return'<';break;

        }

    }

}//Precede

int pow(int a,int b){//求幂函数

    int x;

for(x=1;b>0;b--) x=x*a;

    return x;

}//pow

int Operate(int a,char theta,int b){//操作数a和b进行运算

   switch(theta){

    case'+':return(a+b);

    case'-':return(a-b);

    case'*':return(a*b);

    case'/':return(a/b);

    case'^':return(pow(a,b));

    }

}//Operate

int In(char c){//判断字符c是否为运算符

    if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='^'&&c!='='&&c!='('&&c!=')') return ERROR;

    else return OK;

}//In

int EvaluateExpression(){

    int x,a,b;

    char c,theta;

    SqStack1 OPTR;

    SqStack2 OPND;

    InitStack1(OPTR);

    InitStack2(OPND);

    Push1(OPTR,'#');

    c=getchar();

    while(c!='\\n'){

        x=0;

        if(!In(c))//c是操作数

        {

            while(!In(c))

            {

                x=x*10+c-48;

                c=getchar();

            }

            Push2(OPND,x);

        }

        else//c是算符

        switch(Precede(GetTop1(OPTR),c))

        {

         case'<':Push1(OPTR,c);c=getchar();break;//栈顶元素优先权低

            case'=':Pop1(OPTR,c);c=getchar();break;//脱括号并接受下一个字符

         case'>'://退栈并将运算结果入栈

                Pop1(OPTR,theta);

                Pop2(OPND,b);Pop2(OPND,a);

                Push2(OPND,Operate(a,theta,b));

                break;

        }//switch

    }//while

    return GetTop2(OPND);

}//EvaluateExpression

main()

{    printf("%d",EvaluateExpression());}

//注：本程序存为.cpp方可运行