表达式求值.cpp

数据结构中的表达式求值运算算法实现。数据结构课的要求。

#include<stdio.h>
#include<iostream.h>
#include"表达式求值.h"
//------定义操作符的大小关系
char precede(char a,char b)
{  
	switch(b)
	{ 
	  case '+':
		  switch (a)
		  {
		       case '+':return('>');
			   case '-':return('>');
			   case ')':return('>');
			   case '*':return('<');
			   case '/':return('<');			   
	                   case '(':return('<');			   
			   case '#':return('>');			   
		  };break;
	   case '-':
	       switch (a)
	       {
		       case '+':return('>');
			   case '-':return('>');
			   case '*':return('<');
			   case '/':return('<');
	                   case '(':return('<');
			   case '#':return('>');
			   case ')':return('>');
		   };break;
       case '*':
	        switch (a)
			{
			   case '*':return('>');
			   case '/':return('>');
	                   case '+':return('>');
			   case '-':return('>');
			   case '(':return('<');
			   case ')':return('>');
			   case '#':return('>');
	           };break;
       case '/':
	        switch (a)
	         {
			   case '*':return('>');
			   case '/':return('>');
			  // case '}':return('>');
	           case '+':return('>');
			   case '-':return('>');
			   case ')':return('>');
			   case '#':return('>');
			   case '(':return('<');
	          };break;
       case '(':
	         switch (a)
	          {
			    case '+':return('<');
				case '-':return('<');
				case '*':return('<');
				case '/':return('<');
				case '(':return('<');
				case '#':return('=');//新添
				case ')':return('=');
	           };break;
       case ')':
	         switch (a)
	         {
			    case '+':return('>');
				case '-':return('>');
				case '*':return('>');
				case '/':return('>');
			//	case '}':return('>');
	            case ')':return('>');
				case '#':return('>');
	          };break;
       case '#':
	        switch (a)
	        {
			   case '+':return('<');
			   case '-':return('<');
			   case '*':return('<');
			   case '/':return('<');
			   case '(':return('<');
	                   case '#':return('=');
	          };break;
	}
	return(1);
}
//---四则运算操作
int operate(int m,char w,int n)
{
	switch (w)
	{ 
	case '+':return (m+n);
	case '-':return (m-n);
	case '*':return (m*n);
	case '/':return (m/n);
	};
	return(1);
}

int eval_exp()
{   
	char A[10];//i要小于10
	int a,b,value;         //两操作数及运算值
	char w,r,x;
	sqstktpa opnd;        //操作数
	sqstktpb *optr;      //操作符
    optr=(sqstktpb*)new sqstktpb;  //用new开辟新的运算符堆栈
    inistackb(optr);    //初始化运算符栈 
    pushb(optr,'#');   //将#入栈，以定义运算结束
    inistacka(&opnd);  //初始化操作数栈
	printf("输入算术式组成\n");
	int i=0;	
	w='@';
	while(w!='#')
	{		
      scanf("%c",&w);
	  A[i]=w;
	  i++;
	}
    A[i]='#';
    for(int j=0;j<=i;j++)
	{
		w=A[j];
		if (((w!='#')||(gettopb(optr)!='#')))
		{		
			int ii;
			ii=w-'0';
			if((w>='0')&&(w<='9'))		
			{
				pusha(&opnd,ii);
			}
			else
			{
				char xx=gettopb(optr);
				r=precede(w,xx);		
				switch(r)
				{
				case '<':
					pushb(optr,w);
					break;
				case '=':
					x=popb(optr);
					break;
				case '>':
					x=popb(optr);
					b=popa(&opnd);
					a=popa(&opnd);
					value=operate(a,x,b);
					pusha(&opnd,value);
					break;
				}
			}
		}
	}
	return(popa(&opnd));
};
void main()
{ 
	int expvalue;
	expvalue=eval_exp();
	printf("计算的结果为：");
	printf("%d",expvalue);
}