苗火 Nicholas

[Data structures]EvaluateExpression

2019-9-12 萧 写技术

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

#define MAX 1024

typedef int ElemType;

typedef struct _SqStack{
	ElemType *base;
	ElemType *top;
	int stackSize;
}SqStack;

int InitStack(SqStack *S)
{
	S->base = (ElemType *)malloc(MAX*sizeof(ElemType));
	S->top = S->base;
	S->stackSize = MAX;	
	return 1;
}

ElemType GetTop(SqStack *S)
{
	return *(S->top - 1);
}

int Push(SqStack *S, ElemType e)
{
	if(S->top - S->base >= S->stackSize){
		return 0;
	}
	*(S->top++) = e;
}

int Pop(SqStack *S, ElemType *e)
{
	if(S->top == S->base){
		return 0;
	}else{
		*e = *(--S->top);
		return 1;
	}
}

int StackEmpty(SqStack *S)
{
	if(S->top == S->base){
		return 1;
	}else{
		return 0;
	}
}

int ClearStack(SqStack *S)
{
	S->top = S->base;
	return 1;
}

int PrintStack(SqStack *S)
{
	ElemType *p = S->base;
	while(p != S->top){
		printf("%c", (char)*p);
		p++;
	}
	printf("\n");
	return 1;
}

char OP[] = {7, '+', '-', '*', '/', '(', ')', '#'};
char PRE[][7] = {
	{'>', '>', '<', '<', '<', '>', '>'},
	{'>', '>', '<', '<', '<', '>', '>'},
	{'>', '>', '>', '>', '<', '>', '>'},
	{'>', '>', '>', '>', '<', '>', '>'},
	{'<', '<', '<', '<', '<', '=', ' '},
	{'>', '>', '>', '>', ' ', '>', '>'},
	{'<', '<', '<', '<', '<', ' ', '='}
};

int In(char c, char *array)
{
	int i; 
	for(i=1; i<=array[0]; i++){
		if(c == array[i]){
			return i;
		}	
	}	
	return 0;
}

int Precede(char a, char b)
{
	int na,nb;
	na = In(a, OP) - 1;
	nb = In(b, OP) - 1;
	return PRE[na][nb];
}

int Operate(int a, char x, int b)
{
	int ret;
	switch(x){
		case '+':
			ret = a+b;
			break;
		case '-':
			ret = a-b;
			break;
		case '*':
			ret = a*b;
			break;
		case '/':
			ret = a/b;
			break;
	}	
	return ret;
}

ElemType EvaluateExpression()
{
	SqStack OPTR;
	SqStack OPND;
	int c;
	int x;
	int a;
	int b;
	InitStack(&OPTR);
	InitStack(&OPND);
	Push(&OPTR, '#');	

	c = getchar();
	while(c != '#' || GetTop(&OPTR) != '#'){
		if(!In(c, OP)){
			Push(&OPND, c-'0');
			c = getchar();
		}else{
			switch(Precede(GetTop(&OPTR), c) ){
				case '<':
					Push(&OPTR, c);
					c = getchar();
					break;
				case '=':
					Pop(&OPTR, (int *)&x);
					c = getchar();
					break;
				case '>':
					Pop(&OPTR, &x);
					Pop(&OPND, &b);
					Pop(&OPND, &a);
					Push(&OPND, Operate(a, x, b));
					break;
				default:
					return 0;
					break;
			}
		}
	}
	return GetTop(&OPND);
}

void main()
{
	printf("log.anycle.com\n\n");

	printf("Conversion:\n");
	printf("= %d\n", EvaluateExpression() );
	printf("\n");
}

标签: Data Structures data_structures