计算式求值.cpp

计算式求值栈操作

# include<iostream.h>
# include<string>
# include<stdlib.h>
#  include<conio.h>

int stack_init_size=100;
int stackincreament=10;
typedef int boolean;
char Operator[8]="+-*/()#";
char Optr;
int Opnd=-1;
int result;

typedef struct
{
	int*pbase;
	int *ptop;
	int stacksize;
}stack;


char prioritytable[7][7]=
{
	{'>','>','<','<','<','>','>'},
	{'>','>','<','<','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'<','<','<','<','<','=','0'},
	{'>','>','>','>','0','>','>'},
	{'<','<','<','<','<','0','='}
};

stack initstack()
{
	stack s;
	s.pbase=new int[stack_init_size];
	s.ptop=s.pbase;
	s.stacksize=stack_init_size;
	return s;
}
void destroystack(stack *s)
{
	if(!s->pbase)
	{
		free(s->pbase);
		s->ptop=s->pbase;
	}
}


int gettop(stack s)
{
	return *(s.ptop-1);
}

int push(stack *s,int e)
{
	*(s->ptop++)=e;
	return 1;
}

int pop(stack*s,int *e)
{
	if(s->ptop==s->pbase)
		return 0;
	*e=*--(s->ptop);
	return 1;
}


char checkpriority(char operator_1,char operator_2)
{
	int i,j;
	i=strchr(Operator,operator_1)-Operator;
	j=strchr(Operator,operator_2)-Operator;
	return prioritytable[i][j];
}

boolean isoperator(char ch)
{
	if(strchr(Operator,ch))
		return 1;
	else
		return 0;
}

void getinput()
{
	char buffer[20];
	char ch;
	int index=0;
	ch=getch();
	while(ch!=13 && !isoperator(ch))
	{
		if(ch>='0' && ch<='9')
		{
			cout<<ch;
			buffer[index]=ch;
			index++;
		}
		ch=getch();
	}
	if(ch==13)
		Optr='#';
	else
	{
		Optr=ch;
		cout<<ch;
	}
	if(index>0)
	{
		buffer[index]='\0';
		Opnd=atoi(buffer);
	}
	else
		Opnd=-1;

}

int calc(int a,char theta,int b)
{
	switch(theta)
	{
	case'+':
		return a+b;
	case'-':
		return  a-b;
	case '*':
		return  a*b;
	default:
		if(b==0)
		{
		cout<<"除数不能";
		    return 0;
		}
			else 
				return a/b;
	}
}

bool evaluateexpression()
{
	int temp;
	char theta;
	int itheta;
	int a,b;
//	int topopnd;
//	char topoptr;
	stack optr=initstack();
	stack opnd=initstack();
	if(!push(&optr,'#'))
		return 0;
	getinput();
	while(Optr!='#' || gettop(optr)!='#')
	{
		if(Opnd>=0)
			push(&opnd,Opnd);
		switch(checkpriority(gettop(optr),Optr))
		{
		case '<':
			if(!push(&optr,Optr))
				return 0;
			getinput();
				break;
		case'=':
			pop(&optr,&temp);
			getinput();
			break;
		case'>':
			pop(&optr,&itheta);
			pop(&opnd,&b);
			pop(&opnd,&a);
			theta=char(itheta);
			push(&opnd,calc(a,theta,b));
			Opnd=-1;
			break;
		}
	}
	if(opnd.ptop==opnd.pbase && Opnd<0)
	{
		cout<<endl<<endl<<"感谢使用!"<<endl;
	}
	else
		if(opnd.ptop==opnd.pbase)
			result=Opnd;
		else
		{
			result=gettop(opnd);
			destroystack(&opnd);
			destroystack(&optr);
		}
		return 1;
}


void message()
{
	cout<<"四则运算表达式求值演示(V 0.3)\n"
		<<"****************************************************************\n"
		<<"使用方法: 请从键盘上直接输入表达式,以回车结束\n"
		<<"注0:不输入任何数而直接回车,将退出本次输入.\n"
		<<"注1:本程序暂时不接受除数字键及四则运算之外的任何其他键盘输入.\n"
		<<"注2:不呢程序暂时只能处理正确的表达式,不支持输入负数.\n"
		<<"*****************************************************************\n"
		<<endl;
}

void main()
{
	int i;
	message();
	for(i=1;;i++)
	{
		cout<<"表达式 "<<i<<endl;
		if(evaluateexpression())
			cout<<"="<<result<<endl;
		else
		{
			cout<<"计算中遇到错误\n";
		}
		cout<<"要继续吗?(y/n)\n";
		char t;
		cin>>t;
		if(t!='y')
			return;
	}
}