arithmeticexpressionevaluation.cpp

算术表达式求值 从键盘读入一个合法的算术表达式

#include "stdio.h"
#include "stdlib.h"

#define Init_Size 100
#define ADD 10

typedef struct
{
	int *base;
	int *top;
	int stacksize;
}Num_Stack;

typedef struct
{
	char *base;
	char *top;
	int stacksize;
}Chr_Stack;

void Init(Num_Stack &OPND,Chr_Stack &OPTR,Chr_Stack &TEMP)  //栈的初始化
{
	OPND.base=(int *)malloc(Init_Size*sizeof(int));
	OPND.top=OPND.base;
	OPTR.base=(char *)malloc(Init_Size*sizeof(char));
	OPTR.top=OPTR.base;
	TEMP.base=(char *)malloc(Init_Size*sizeof(char));
	TEMP.top=TEMP.base;
	OPND.stacksize=OPTR.stacksize=TEMP.stacksize=Init_Size;
}

void PushChr(Chr_Stack &S,char c)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(char *)realloc(S.base,(Init_Size+ADD)*sizeof(char));
	}
	*S.top=c;
	S.top++;
}

void PushNum(Num_Stack &S,int n)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(int *)realloc(S.base,(Init_Size+ADD)*sizeof(int));
	}
	*S.top=n;
	S.top++;
}

char GetTopChr(Chr_Stack &S)
{
	char c;
	if(S.base==S.top)
	{
		printf("error\n");
		exit(0);
	}
	c=*(S.top-1);
	return c;
}

int GetTopNum(Num_Stack &S)
{
	int n;
	if(S.base==S.top)
	{
		printf("error\n");
		exit(0);
	}
	n=*(S.top-1);
	return n;
}

bool In(char c)                                 //判断c是否为操作符
{
	if(c>='('&&c<='9'&&c!=','&&c!='.'||c=='#')
	{
		switch(c)
		{
		case'+':return true;//  break;
		case'-':return true;//  break;
		case'*':return true;//  break;
		case'/':return true;//  break;
		case'(':return true; // break;
		case')':return true; // break;
		case'#':return true; // break;
		default:return false;
		}
	}
	else
	{
		printf("error:不可识别的字符\n");
		exit(0);
	}
}

int GetNum(Chr_Stack &S)        //将字符串转化为数字
{
	char *p;
	int num=0;
	for(p=S.base;p!=S.top;p++)
	{
		num=10*num+(*p-'0');
		*p=0;
	}
	S.top=S.base;
	return num;
}

int Precede(char theta1,char theta2)              //判断运算符优先级
{
	if(theta1=='+'||theta1=='-')
	{
		if(theta2=='*'||theta2=='/'||theta2=='(')
		{
			return '<';
		}
		else
		{
			return '>';
		}
	}
	if(theta1=='*'||theta1=='/')
	{
		if(theta2=='(')
		{
			return '<';
		}
		else
		{
			return '>';
		}
	}
	if(theta1=='(')
	{
		if(theta2==')')
		{
			return '=';
		}
		else 
			if(theta2=='#')
			{
				printf("error:括号不匹配(多余'(')\n");
				exit(0);
			}
			else
			{
				return '<';
			}
	}
	if(theta1==')')
	{
		if(theta2=='(')
		{
			printf("error:括号间缺少运算符\n");
			exit(0);
		}
		else
		{
			return '>';
		}
	}
	if(theta1=='#')
	{
		if(theta2=='#')
		{
			return '=';
		}
		else
			if(theta2==')')
			{
				printf("error:括号不匹配(多余')')\n");
				exit(0);
			}
			else
			{
				return '<';
			}
	}
}

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'/':
		{
			if(b==0)
			{
				printf("error:除数不能为零\n");
				exit(0);
			}
			else
			{
				result=a/b; 
				break;
			}
		}
	}
	return result;
}

void OutPutChr(Chr_Stack &S)     //输出OPTR栈
{
	char *p;
	for(p=S.base;p!=S.top;p++)
	{
		printf("%c",*p);
	}
}

void OutPutNum(Num_Stack &S)     //输出OPND栈
{
	int *p;
	for(p=S.base;p!=S.top;p++)
	{
		printf("%d ",*p);
	}
}

void main()
{
	char c;
	char theta;
	int a,b;
	int sign;
	Num_Stack OPND;
	Chr_Stack OPTR,TEMP;
	Init(OPND,OPTR,TEMP);
	printf("输入计算表达式,以#作为开始与结束标志\n例:#1+1#\n");
	c=getchar();
	printf("OPTR栈\t\t\tOPND栈\n");
	PushChr(OPTR,'#');
	c=getchar();
	if(c=='#'||GetTopChr(OPTR)!='#')
	{
		printf("error:未输入计算表达式\n");
		exit(0);
	}
	while(c!='#'||GetTopChr(OPTR)!='#')
	{
		sign=0;
		while(!In(c))                     //非操作符则进TEMP栈
		{
			PushChr(TEMP,c);
			c=getchar();
			sign++;
		}
		if(sign)
		{
			PushNum(OPND,GetNum(TEMP));    //操作数进OPND栈
		}
		OutPutChr(OPTR);                   //输出当前的OPTR栈
		printf("\t\t\t");
		OutPutNum(OPND);                   //输出当前的OPND栈
		printf("\n");
		switch(Precede(GetTopChr(OPTR),c))  //判断操作符优先级并进行相应操作
		{
		case'<':                             //操作符进栈
			{
				PushChr(OPTR,c);
				c=getchar();
				break;
			}
		case'=':                             //括号推栈
			{
				*OPTR.top--;
				c=getchar();
				break;
			}
		case'>':                              //执行一次运算
			{
				theta=*(--OPTR.top);
				b=*(--OPND.top);
				if(OPND.top==OPND.base)
				{
					printf("error:多余运算符\n");
					exit(0);
				}
				a=*(--OPND.top);
				PushNum(OPND,Operate(a,theta,b));
			}
		}
	}
	printf("结果为%d\n",GetTopNum(OPND));
}