表达式求值

表达式求值并输出逆波兰表达式

#include <stdio.h>
#include<stdlib.h>
#include <conio.h>


#define OK          1
#define ERROR       0
#define OVERFLOW    -2

typedef char SElemType; 
typedef int ElemType;    
typedef int  Status;

#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10

typedef struct//存放运算符的栈
{
    SElemType *base;
	SElemType *top;
    int  stacksize;
}SqStack_c;
typedef struct//存放数字的栈
{
    ElemType *base;
	ElemType *top;
    int   stacksize;
}SqStack;
typedef struct//存放后缀表达式
{
	SElemType data[STACK_INIT_SIZE];
	int front;
	int rear;
}SqQueue;
Status Init_SqQueue(SqQueue *l)//队列的初始化
{
	l->front=0;
	l->rear=0;
	return OK;
}
void EnQueue(SqQueue *l,SElemType e)//入队列
{
	if((l->rear+1)%STACK_INIT_SIZE==l->front)//如果队列满了
	{
		printf("队列已满!\n");
		return ;
	}
	l->data[l->rear]=e;
	l->rear=(l->rear+1)%STACK_INIT_SIZE;//rear后移一个位置
}
void queueTraverse(SqQueue *l)//遍历队列
{
    int i=l->front;           //从头开始遍历
    printf("后缀表达式为:");
    while(i!=l->rear)     //如果没有到达rear位置，就循环
    {
        printf("%c  ", l->data[i]);
        i=(i+1)%STACK_INIT_SIZE;              //移到下一位置
    }
    printf("\n");
}
Status InitStack_c(SqStack_c *S)//初始化运算符栈
{
    S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//申请空间
    if(!S->base)            
        exit(OVERFLOW);
    S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
    return OK;
}
Status InitStack(SqStack *S)//初始化数字栈
{
    S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//申请空间
    if(!S->base)
        exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}
SElemType GetTop_c(SqStack_c *S)//取运算符栈的栈顶元素
{
    if(S->top ==S->base)//当栈为空
        return ERROR;
    return *(S->top-1);
}
ElemType GetTop(SqStack *S)//取数字栈的栈顶元素
{
    if(S->top==S->base)//当栈为空
        return ERROR;
    return *(S->top-1);
}
Status Push_c(SqStack_c *S, SElemType e)//运算符入栈
{
    if(S->top-S->base>=STACK_INIT_SIZE)//当运算符栈空间已满是，追加空间
	{
        S->base= (SElemType*)realloc(S->base, (STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
        if(!S->base)
            exit(OVERFLOW);
		S->top=S->base+S->stacksize;//top的为只要随之改变
        S->stacksize+=STACKINCREMENT;
    }
    *(S->top)=e;
	S->top++;//top后移
    return OK;
}
Status Push(SqStack *S, ElemType e)//数字入栈
{
    if(S->top-S->base>=STACK_INIT_SIZE)//当数字栈空间已满是，追加空间
	{
        S->base = (ElemType*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(ElemType));
        if(!S->base)
            exit(OVERFLOW);
        S->top=S->base+S->stacksize;//top的为只要随之改变
        S->stacksize += STACKINCREMENT;
    }
    *(S->top)=e;
    S->top++;//top后移
    return OK;
}
Status Pop_c(SqStack_c *S, SElemType *e)//将栈顶元素弹出栈
{
    if(S->top==S->base)//当栈为空
        return ERROR;
	S->top--;//先top向下移动一个位置，再将那个位置的值带回去
    *e =*(S->top);
	
    return OK;
}
Status Pop(SqStack *S, ElemType *e)//将栈顶元素弹出栈
{
    if(S->top==S->base)//当栈为空
        return ERROR;
	S->top--;//先top向下移动一个位置，再将那个位置的值带回去
    *e =*(S->top);
	
    return OK;
}

char Precede(char a, char b)//优先级的比较
{
    int i,j;
    char pre[7][7]={//列是表达式中左边的，行是刚刚输入的
		/*+*/	{'>','>','<','<','<','>','>'},
		/*-*/	{'>','>','<','<','<','>','>'},
		/***/	{'>','>','>','>','<','>','>'},
		/*/*/	{'>','>','>','>','<','>','>'},
		/*(*/	{'<','<','<','<','<','=','0'},
		/*)*/	{'>','>','>','>','0','>','>'},
		/*#*/	{'<','<','<','<','<','0','='}};/*运算符之间的优先级制作成一张表格*/
		switch(a)
		{
        case '+': i=0; break;
        case '-': i=1; break;
        case '*': i=2; break;
        case '/': i=3; break;
        case '(': i=4; break;
        case ')': i=5; break;
        case '#': i=6; break;
		default:  i=-1;
		}
		switch(b)
		{
        case '+': j=0; break;
        case '-': j=1; break;
        case '*': j=2; break;
        case '/': j=3; break;
        case '(': j=4; break;
        case ')': j=5; break;
        case '#': j=6; break;
		default:  i=-1;
		}
		return pre[i][j];
}
int Operate(int a, char theta,int b)//运算结果
{
    int result;
    switch(theta) 
	{
	case '+': result = a + b; break;
	case '-': result = a - b; break;
	case '*': result = a * b; break;
	case '/': result = a / b; break;
    }
    return result;
}
int isdigit(char c)//判断是否为数字
{
	if(c>='0'&&c<='9')
		return 1;
	else
		return 0;
}
int EvaluateExpression()
{
    int n,a,b;
    char x,theta,c;                               
    SqStack_c  OPTR;                             
    SqStack  OPND; 
	SqQueue Q;
	Init_SqQueue(&Q);
    InitStack_c(&OPTR);      
    Push_c(&OPTR,'#');//#界限符
    InitStack(&OPND);
	
		c=getchar();
		x=GetTop_c(&OPTR);
		while(c!='#'||x!='#')
		{
			if(isdigit(c)) 
			{
				EnQueue(&Q,c);
				n=c-'0'; 
				Push(&OPND,n);
				c=getchar();
			}    
			else
			{
				
				switch(Precede(x,c))
				{
                case'<':                 
                    Push_c(&OPTR,c);
					c=getchar();
                  
                    break;
                case'=':
                    Pop_c(&OPTR,&x);
					c=getchar();
                    break;
                case'>':                                  
                    Pop_c(&OPTR, &theta);
					EnQueue(&Q,theta);
                    Pop(&OPND,&b);
                    Pop(&OPND,&a);
                    Push(&OPND, Operate(a, theta, b));
                    break;
				default: ;
				}
			}
			x=GetTop_c(&OPTR);
		}
    n=GetTop(&OPND);
	queueTraverse(&Q);
    return n;
}

void main()
{
    int c;
    printf("请输入表达式，当输入#时结束:");
    c=EvaluateExpression();
    printf("Result=%d\n",c);
    getch();
}