中缀表达式求值.cpp

中缀表达式求值

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

//#define maxnum 100;
char num[10];
int op=0;

struct optr//操作符栈定义
{
   int top;
   char optrc[100];
}OPTR;
struct opnd//操作数定义
{
   double opndc[100];
   int top;
}OPND;

char Optr[7][7]=//运算符优先关系
{
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=',' '},
		{'>','>','>','>',' ','>','>'},
		{'<','<','<','<','<',' ','='}
};
void InitStackOPTR(optr &OPTR)//初始化运算符栈
{
  OPTR.top=-1;
}
void InitStackOPND(opnd &OPND)//初始化数据栈
{
  OPND.top=-1;
}
void PushOPND(opnd &OPND,double a)//数据进栈
{
   OPND.top++;
   OPND.opndc[OPND.top]=a;
}
void PushOPTR(optr &OPTR,char r)//操作符进栈
{
   OPTR.top++;
   OPTR.optrc[OPTR.top]=r;
}
int opterdata(char c)//判断输入的字符是否为运算符
{

   switch(c)
   {
   case '+':return 1;
   case '-':return 2;
   case '*':return 3;
   case '/':return 4;
   case '(':return 5;
   case ')':return 6;
   case '#':return 7;
   default:return -1;
   }
}
char Precede(char e,char f)//比较优先级
{
   return(Optr[opterdata(e)-1][opterdata(f)-1]);
}

double GetTopOPND(opnd &OPND)//获得运算符栈的栈顶元素
{
  return(OPND.opndc[OPND.top]);
}
char GetTopOPTR(optr &OPTR)//获得运算数栈的栈顶元素
{
  return(OPTR.optrc[OPTR.top]);
}
char PopOPTR(optr &OPTR)//去掉运算符栈顶元素，并返回
{
   char x;
   x=OPTR.optrc[OPTR.top];
   OPTR.top--;
   return(x);
}
double PopOPND(opnd &OPND)//去掉运算数栈顶元素，并返回
{
   double v;
   v=OPND.opndc[OPND.top];
   OPND.top--;
   return(v);
}
double Operate(double i,char ope,double j)//运算
{
   if (ope=='+')
	   return(i+j);
   else if(ope=='-')
	   return(i-j);
   else if(ope=='*')
	   return(i*j);
   else if(ope=='/')
	   return(i/j);
}
double EvaluateExpression()//求值函数
{
   InitStackOPTR(OPTR);
   PushOPTR(OPTR,'#');
   InitStackOPND(OPND);
   char c;
   cin>>c;
   while(c!='#' || GetTopOPTR(OPTR)!='#')
   {

	   if(opterdata(c)==-1)
	   {  
		   do
		   {
			   num[op]=c; op++;cin>>c;
		   }while(c>='0'&&c<='9');
		   PushOPND(OPND,atof(num));  op=0; 
		   for(int h=0;h<10;h++)
			   num[h]=0;
	   }	   
	   else
	   {
	     
		  switch(Precede(GetTopOPTR(OPTR),c))
		  {
		     case '<':PushOPTR(OPTR,c); cin>>c;break;
		     case '=':PopOPTR(OPTR); cin>>c;break;
             case '>':PushOPND(OPND,Operate(PopOPND(OPND),PopOPTR(OPTR),PopOPND(OPND)));break;
		  }

	   }
   }
   return(GetTopOPND(OPND));
}
void main()
{

   cout<<"请输入表达式（以'#'结束）"<<endl;
   cout<<EvaluateExpression()<<endl;
}