表达式求值.cpp

/* author: qiaoger from: Computer Science Department of SiChuan University date: 2008-3-2

/*

   author: qiaoger 
	 from:   Computer Science Department of SiChuan University
	 date:   2005-3-27

	求算术表达式（整数）的值（中序法）
*/

#include<stdio.h>
#include<math.h>
#include<string.h>
const int MAX=100;//假设栈足够大
char StackOperator[MAX]; //运算符栈
int StackOperand[MAX]; //数据栈
int top1; //运算符栈 栈顶指针
int top2;  //数据栈 栈顶指针


void init()//建栈 并初始化
{
	top1=top2=-1;;
	top1++;
	StackOperator[top1]='=';
}

bool isEmptyOperator()
{
	if(top1==-1)
		return true;
	else
		return false;
}

bool isEmptyOperand()
{
	if(top2==-1)
		return true;
	else
		return false;
}

char popOperator()
{
	char temp;
	temp=StackOperator[top1];
  top1--;
	//printf("%c 出操作符栈\n",temp);
		return temp; 
}
int popOperand()
{
	int temp;
	temp=StackOperand[top2];
  top2--;
	//printf("%d 出操作数栈\n",temp);
		return temp; 
}

void pushOperator(char ch)
{
	top1++;
	StackOperator[top1]=ch; 
	//printf("%c 进操作符栈\n",ch);
}

void pushOperand(int n)
{
	top2++;
	StackOperand[top2]=n; 
	//printf("%d 进操作数栈\n",n);
}

int Isp(char ch) //各操作符的 栈内优先级别
{
	switch(ch)
	{
		case '=':
			return 0;
		case '(':
			return 1;
		case '^':
			return 7;
		case '*':
		case '/':
		case '%':
			return 5;
		case '+':
		case '-':
			return 3;
		case ')':
			return 8;
		default:
			return -1;
	}
}

int Icp(char ch) //各操作符的 栈外优先级别
{
	switch(ch)
	{
		case '=':
			return 0;
		case '(':
			return 8;
		case '^':
			return 6;
		case '*':
		case '/':
		case '%':
			return 4;
		case '+':
		case '-':
			return 2;
		case ')':
			return 1;
		default:
			return -1;
	}
}

bool isOperator(char ch)//判断是否是合法的操作符
{
	if(ch=='('||ch==')'||ch=='^'||ch=='*'||ch=='/'||ch=='%'||ch=='+'||ch=='-')
		return true;
	else
		return false;
}

void warn()
{
	printf("The Expression is not legal !\n");
		return ;
}

int run(int a,char ch,int b)//各操作符计算
{
	int  r;
	r=-1;
	switch (ch)
	{
		case '^' :
		{
			r=(int)pow(a,b);
			break;
		}
		case '%':
		{
			r=a%b;
			break;
		}
		case '*':
		{
			r=a*b;
			break;
		}
		case '/':
		{
			r=a/b;
			break;
		}
		case '+':
		{
			r=a+b;
			break;
		}
		case'-':
		{
			r=a-b;
			break;
		}
		default: break;
	}
	return r;
}

void computer(char *expression)//判断 并计算表达式
{
	char *p,ch,ch2;
	int temp,a,b;
  
	init();
	p=expression;
  temp=0;
	ch=*p;
	while(ch!='=')
	{
		if(ch>='0'&&ch<='9')//读入操作数
		{
			temp=ch-'0';
			p++;
			ch=*p;
			while(ch>='0'&&ch<='9')
			{
				temp=temp*10+(ch-'0');
				p++;
				ch=*p;
			}
      pushOperand(temp);//
      p--;
		}
		else
		  if(!isOperator(ch))//非法字符
			{
				//printf("非法操作符\n");
				warn();
				return ;
			}
			else //合法的操作符
			{
				ch2=popOperator();
        if(ch == ')')// 输入“)”
				{
					while(ch2!='(')
					{
						if(top1<0)//栈中不足一个操作符
						{
							//printf("缺操作符\n");
							warn();
							return ;
						}

						if(top2<1)//栈中不足两个操作数
						{
							//printf("缺操作数\n");
							warn();
							return ;
						}
						b=popOperand();
						a=popOperand();
						temp=run(a,ch2,b);
						pushOperand(temp);
						ch2=popOperator();
					}
				}
        else
				if(Icp(ch) > Isp(ch2))
				{
					pushOperator(ch2);//还原
					pushOperator(ch);
				}
        else
				if((Icp(ch) < Isp(ch2)))
				{
					while(Icp(ch) < Isp(ch2) )
					{
						if(top1<0)//栈中不足一个操作符
						{
						//	printf("缺操作符\n");
							warn();
							return ;
						}

						if(top2<1)//栈中不足两个操作数
						{
							//printf("缺操作数\n");
							warn();
							return ;
						}
						b=popOperand();
						a=popOperand();
						temp=run(a,ch2,b);
						pushOperand(temp);
						ch2=popOperator();
						}
						pushOperator(ch2);
						pushOperator(ch);
					}

		
					//printf(": %c %c\n",ch2,ch);
				
			}	
		p++;
		ch=*p;
	}
	//计算余下的操作符
		while(top1>0)
		{
		  ch=popOperator();		
		  if(top2<1)//栈中不足两个操作数
			{
			  //printf("缺操作数\n");
			  warn();
			  return ;
			}
      b=popOperand();
		  a=popOperand();
		  temp=run(a,ch,b);
		  pushOperand(temp);
		}

	printf("%d\n",popOperand());
}

int main()
{

  char Expression[MAX*2];
	printf("******** qiaoger Expression 计算整形表达式的值 *******\n");
	printf("****  支持操作符：+、－、*、/、%%、^（幂）;支持 () ****\n");
	printf("输入“＃”退出程序\n");
	printf("请输入表达式(如 (1+2)*3-27/9= ) :\n");
	while(scanf("%s",Expression)==1)
	{
		if(strcmp(Expression,"#")==0)
			break;
	   computer(Expression);
		printf("****  支持操作符：+、－、*、/、%%、^（幂）;支持 () ****\n");
	  printf("输入“＃”退出程序\n");
	  printf("请输入表达式(如 (1+2)*3-27/9= ) :\n");
  }
	return 1;
}