cpp1.cpp

简单的表达式求值算法

/*
*程序实现：带括号多位数表达式求值运算
*author：  Li Zhenchao
*/

#include<stdio.h>
#include<stdlib.h>
#include"c:\seqstack.h"     /*使用已定义的栈的头文件*/


int In(char ch)          //判断输入字符是否为运算符
{
	int i=0;
	char  OPSet[8]={'+','-','*','/','(',')','#','\0'};  /*运算符表*/
	while(OPSet[i]!='\0')
	{
		if(OPSet[i]==ch)
			return 1;
		else  
			i++;
	}
	
		return 0;
}

int Getnumber(char ch)         /*将输入数字字符转为数字表示*/
{
	return ch-'0';
}


int fun(char ch)         /*返回输入运算符在运算符表中的位置*/
{
	int k=0;
	char  OPSet[8]={'+','-','*','/','(',')','#','\0'};
	while(OPSet[k]!='\0')
	{
		if(ch==OPSet[k])
		{
			return k;
		}
		else k++;
	}
}


/*建立二维表存储两运算符之间的优先级关系，并根据输入传回它们的优先级比较关系
	+	-   *	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	>	>	>	>	>	=	X
)	>	>	>	>	X	>	>
#	<	<	<	<	<	X	=

*/
char Compare(char optr,char ch)      
{
	int i,j;
	char a[7][7]=
	{
		{'>','>','<','<','<','>','>'},                            
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=','X'},
		{'>','>','>','>','X','>','>'},
		{'<','<','<','<','<','X','='}
	};
	i=fun(optr);
	j=fun(ch);
	return a[i][j];
}




int Execute(int a,char op,int b)       //根据输入的运算符和运算数进行相应运算，返回结果
{
	switch(op)
	{
	case'+':
		return a+b;
		
	case'-':
		return a-b;
	
    case'*':
		return a*b;
		
	case'/':
		if(b==0)
		{   
			printf("ERROR!,除数为0!\n");
			exit(0);
		}
     	else
			return a/b;
		
	default:
		;
	}
}


 int Expevaluation()              //接受输入表达式进行计算，返回运算结果
{
	char ch,op;
	int n,a,b,v,j;
	Init(&OVS);
	Init(&OPTR);
	Push(&OPTR,'#');
	printf("\n请输入一个表达式串，以#为结束符\n");
	ch=getchar();
	while(ch!='#'||Gettop(OPTR)!='#')
	{
		
		if(!In(ch))                                 /*将输入字符转化为十进制数字，并将最后转化结果入栈*/
		{
		    n=0;
		while(!In(ch))
		{
			n=n*10+Getnumber(ch);
			ch=getchar();

		}
		Push(&OVS,n);
		}
		else                                         /*如为运算符则与栈顶字符比较优先级*/
			switch(Compare(Gettop(OPTR),ch))
		{
			case'<':                     /* 小于 直接入运算符栈，取下一字符*/
				Push(&OPTR,ch);
				ch=getchar();
				break;
			case'>':                     /* 大于  将栈顶运算符出栈，出栈操作数进行运算*/
			
				Pop(&OPTR,&op);
				Pop(&OVS,&b);
				Pop(&OVS,&a);
				v=Execute(a,op,b);
				Push(&OVS,v);
				break;
			case'=':                   /* 等于，直接取下一字符*/            
				Pop(&OPTR,&op);
				ch=getchar();
				break;
			case'X':
				printf("ERROR! 输入格式错误!\n");         
				exit(0);
		}
		
	}
	v=Gettop(OVS);
	return(v);
}


  void main()
{
	
	int x;
	x=Expevaluation();
    printf("表达式运算结果为%d\n",x);
}