main.c

表达式运算（计算器）

#include <stdio.h>
#include <stdlib.h>
#define OK 0
#define ERROR -1
#define OVERFLOW -2
#define FALSE 0
#define TRUE !(FALSE)
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef int Status;
typedef int Bool;
typedef int SElemType;
typedef struct
 {
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;//栈的元素类型
OPTRPrecede[][7]={'>','>','<','<','<','>','>',
				 '>','>','<','<','<','>','>',
				 '>','>','>','>','<','>','>',
				 '>','>','>','>','<','>','>',
				 '<','<','<','<','<','=',' ',
				 '>','>','>','>',' ','>','>',
				 '<','<','<','<','<',' ','='};//运算符优先组存储

Status InitStack(SqStack *s)
{//构造一个空栈s
	s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if (!s)
		exit(OVERFLOW);//存储分配失败
	s->top=s->base;
	s->stacksize=STACK_INIT_SIZE;
	return OK;
}
Status Push(SqStack *s, SElemType e)
{//插入元素e为新的栈顶元素
	if (s->top-s->base>=s->stacksize){
		s->base=(SElemType*)realloc(s->base, 
			(s->stacksize+STACKINCREMENT)*sizeof(SElemType));
		if (!s->base) 
			exit(OVERFLOW);
		s->top=s->base+s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*s->top++=e;
	return OK;
}//入栈
Status Pop(SqStack *s, SElemType *e)
{//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK;否则返回ERROR;
	if (s->top==s->base)
		return ERROR;
	*e=*--s->top;
	return OK;
}
Status StackEmpty(SqStack s)
{
	return (s.top-s.base==0);
}//出栈
Status GetTop(SqStack s, SElemType *e)
{
	if (StackEmpty(s))
		return ERROR;
	*e=*(s.top-1);
	return OK;
}//取栈顶
Bool IsOPTR(int e)
{
	switch (e)
	{
	case '+':case '-':case '*':case '/':
	case '(':case ')':case '#':
		return TRUE;
	}
	return FALSE;
}//判断是否是运算符
char Precede(int t, int c)
{
	int x, y;
	switch (t)
	{
		case '+': x=0; break;
		case '-': x=1; break;
		case '*': x=2; break;
		case '/': x=3; break;
		case '(': x=4; break;
		case ')': x=5; break;
		case '#': x=6; break;
	}
	switch (c)
	{
		case '+': y=0; break;
		case '-': y=1; break;
		case '*': y=2; break;
		case '/': y=3; break;
		case '(': y=4; break;
		case ')': y=5; break;
		case '#': y=6; break;
	}
	return OPTRPrecede[x][y];
}//判断优先组
int Operate(int a, int theta, int b)
{
	switch (theta){
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		case '/': return a/b;
	}
	return ERROR;
}//计算表达式
int main()
{
	SqStack optr, opnd;
	int a, b, theta;
	int c, t;
	InitStack(&optr);//运算符栈
	InitStack(&opnd);//运算数栈
	Push(&optr, '#');
	printf("表达式求值：\n");
	printf("输入表达式(输入元素只能为个位数)：\n");
	c=getchar();
	while (c!='#' || (GetTop(optr, &t), t!='#'))
	{
		if (!IsOPTR(c))
		{
			Push(&opnd, c-'0');	
			printf("%d ",c-48);			
			c=getchar();
		}//不是运算符则进栈
		else
		{
			switch (GetTop(optr, &t), Precede(t, c)){
				case '<'://栈顶元素优先权低
					Push(&optr, c);					
					c=getchar();
					break;
				case '='://脱括号并接收下一字符
					Pop(&optr, &c);
					c=getchar();
					break;
				case '>'://退栈并将元素结果入栈
					Pop(&optr, &theta);
					Pop(&opnd, &b);
					Pop(&opnd, &a);	
					printf("%c ",theta);				
					Push(&opnd, Operate(a, theta, b));					
					break;
			}
		}
	}
	GetTop(opnd, &t);
	printf("\n");
	printf("输出结果：\n");
	printf("%d\n", t);
}