学步园

/*=========================================================================
#    FileName: expression.c
# Description: 表达式求值,表达式以'#'结束，默认输入无误且无换行，但可以有空格
			   可以计算多位数，但不可有负数和小数
#  LastChange: 2012-06-03 00:38:36
=========================================================================*/
#include <stdio.h> 
#include <stdlib.h>  //malloc() 
#include <string.h>  //memcpy() 

/* C语言没有bool类型，自己定义一个 */
typedef int bool;
#define TRUE  1
#define FALSE 0
#define OK    1
#define FAIL  0

struct Node {
    void *pValue;
    struct Node *pFront;
};

typedef struct Node Node;

typedef struct {
    Node *top;
    size_t TypeSize;		/* date byte */
}Stack;

bool InitStack(Stack * S, const size_t data_byte) {
	if( S == NULL || data_byte <= 0) return FAIL;
    
    S->top = NULL;
    S->TypeSize = data_byte;
    
    return OK;
}

bool IsEmpty(const Stack * const S) {
    if(S->top == NULL) return TRUE;
    else return FALSE;
}

bool Push(Stack * S, const void *e) {
	if(S == NULL || e == NULL) return FAIL;

    Node *ptmp=S->top;	

    if( (S->top = malloc(sizeof(Node))) == NULL) return FAIL;
    if( (S->top->pValue = malloc(S->TypeSize)) == NULL) return FAIL;
    memcpy(S->top->pValue, e, S->TypeSize);

    S->top->pFront = ptmp;
    return OK;
}

bool Pop(Stack *S, void *e) {
	if(S == NULL || e == NULL) return FAIL;
    
    if(!IsEmpty(S)) {
		memcpy(e, S->top->pValue, S->TypeSize); /* 通过参数返回值 */
		free(S->top->pValue);
		Node *ptmp = S->top->pFront; /* 前一个元素 */
		free(S->top);
		S->top = ptmp;
		return OK;
    }
    return FAIL;
}

bool GetTop(const Stack *S,void *e) {
	if(S == NULL || e == NULL) return FAIL;
    if(!IsEmpty(S)) {
		memcpy(e, S->top->pValue, S->TypeSize); /* 通过参数返回值 */
		return OK;
	}
    return FAIL;
}


char Priority[8][8] = {
    {'>','>','<','<','<','<','>','>'},
    {'>','>','<','<','<','<','>','>'},
    {'>','>','>','>','>','<','>','>'},
    {'>','>','>','>','>','<','>','>'},
    {'>','>','>','>','>','<','>','>'},
    {'<','<','<','<','<','<','=',' '},
    {'>','>','>','>','>',' ','>','>'},
    {'<','<','<','<','<','<',' ','='}
};


int GetNumber(char c) {
    switch(c) {
        case '+': return 0;
        case '-': return 1;
        case '*': return 2;
        case '/': return 3;
        case '%': return 4;
        case '(': return 5;
        case ')': return 6;
        case '#': return 7;
        default:  exit(0);
    }
}

char Precede(char x1,char x2) {
    int i = GetNumber(x1);
    int j = GetNumber(x2);
    return Priority[i][j];
}

bool IsOperator(char c) {
    switch(c) {
        case '+' : return TRUE;
        case '-' : return TRUE;
        case '*' : return TRUE;
        case '/' : return TRUE;
        case '%' : return TRUE;
        case '(' : return TRUE;
        case ')' : return TRUE;
        case '#' : return TRUE;
        default:   return FALSE;
    }
}

Stack RealInputStack,ReverseStack,StackAfterDeal,FinalStack;

enum OperatorOrNot { No,Yes };

typedef struct {
    long int eValue;
    enum OperatorOrNot optrOrNot;
}InputElem;

void ReceiveInput() {
    char c = 0, n = 0;
	InputElem tmp;
    tmp.eValue = 0;
    tmp.optrOrNot = No;

    InitStack(&RealInputStack,sizeof(InputElem));
    while((c = getchar()) != '#') {
		if(c == ' ') continue;
        if(IsOperator(c)) {
            n = 0;
            tmp.optrOrNot = Yes;
            tmp.eValue = c;
        }
        else if(n == 1) {
            Pop(&RealInputStack,&tmp);
            tmp.eValue = tmp.eValue * 10 + (c - 48);
        }
        else if(n == 0) {
            n = 1; 
            tmp.optrOrNot = No;
            tmp.eValue = c - 48;
        }
        Push(&RealInputStack,&tmp);
    }
	tmp.optrOrNot = Yes;
	tmp.eValue = c;
	Push(&RealInputStack,&tmp);
}

bool GetFinalStack() {
    InputElem tmp;
    tmp.eValue = 0;
    tmp.optrOrNot = No;

    InitStack(&FinalStack,sizeof(InputElem));

    if(IsEmpty(&RealInputStack)) return FAIL;

    while(!IsEmpty(&RealInputStack)){
        Pop(&RealInputStack,&tmp);
        Push(&FinalStack,&tmp);
    }
    return OK;
}

long int Evaluate(long int opnd1,char optr,long int opnd2) {
    switch(optr) {
        case '+': return (opnd1 + opnd2);
        case '-': return (opnd1 - opnd2);
        case '*': return (opnd1 * opnd2);
        case '/': return (opnd1 / opnd2);
        case '%': return (opnd1 % opnd2);
        default:  return 0;
    }
}

long int EvaluateExpression(long int *result) {
    char c = 0, optr = 0,temp = '#';
    long int opnd1 = 0,opnd2 = 0,tmpresult = 0;

    InputElem tmp;
    tmp.eValue = 0;
    tmp.optrOrNot = No;

    Stack OPND,OPTR;     
    InitStack(&OPND,sizeof(long int));
    InitStack(&OPTR,sizeof(char));
    Push(&OPTR,&temp);

    ReceiveInput();
    GetFinalStack();


    Pop(&FinalStack,&tmp);
    GetTop(&OPTR,&c);

    while( !((tmp.eValue == '#') && (tmp.optrOrNot == Yes)) || c != '#')
    {
        if(tmp.optrOrNot == No) {
            Push(&OPND,&tmp.eValue);
            Pop(&FinalStack,&tmp);
        } //if 
        else {
            switch( Precede(c,(char)tmp.eValue)) {
                case '<': temp = (char)tmp.eValue; 
                          Push(&OPTR, &temp); 
                          Pop( &FinalStack, &tmp );
                          break;
                case '=': Pop( &OPTR,&c);
                          Pop( &FinalStack, &tmp );
                          break;
                case '>': Pop( &OPND, &opnd2 );
                          Pop( &OPND, &opnd1 );
                          Pop( &OPTR, &optr );
						  /*printf("%d %c %d = ",opnd1,optr,opnd2);*/
                          tmpresult = Evaluate(opnd1,optr,opnd2);
						  /*printf("%ld\n",tmpresult);*/
                          Push(&OPND,&tmpresult);
						  break;
                default:  return FAIL; 
            } //switch 
        } //else 
		GetTop(&OPTR,&c);
    } //while 
    *result = tmpresult;
    return OK;
}


int main(void)
{
    long int result = 0;
	printf( "Please input the expression:\n" );
	EvaluateExpression(&result);
	printf( "The result is : %5ld\n",result );
    return 0;
}