学步园

#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef double SElemType;
/////////////////////////////////////////////////////////////////////////////////
                           /*以下为栈的操作*/

typedef struct SqStack    //栈的顺序存储结构
{
 SElemType *base;
 SElemType *top;
 int stacksize;
}SqStack;
void InitStack (SqStack &S)//构造一个空栈
{
 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));//分配储存空间
 if(!S.base) exit (-1);          //空间分配失败
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;        //空间初始分配
}//InitStack
bool GetTop (SqStack S,SElemType  &e)
{      //若栈不空，则用e返回S的栈顶元素，并返回true；否则返回false
 if(S.top==S.base)
  return false;
 e=*(S.top-1);
 return true;
}//GetTop
bool Push(SqStack &S,SElemType e)
{        //插入元素为e的新的栈顶元素
 if(S.top-S.base>=S.stacksize)
 {       //栈满，追加存储空间
  S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
   if(!S.base)   
    exit(-1);  //存储空间分配失败
   S.top=S.base+S.stacksize;//此处内存有可能重新分配,S.base地址有可能会变，此句不能省
   S.stacksize+=STACKINCREMENT;
 }
 *S.top++=e;//top自增
 return true;
}// Push
bool  Pop(SqStack &S,SElemType &e)//若栈不空，则删除S的栈顶元素，用e返回其值
{
 if(S.top==S.base)
  return false;
 e=*--S.top;     //删除一个元素,top减一
 return true ;
}// Pop
/////////////////////////////////////////////////////////////////////////////////////////////////
                                  /*以下为判断符号优先级的函数*/

char Precede(char a1 ,char a2)//判定运算符的优先级。
{        //根据课本p53页的表3.1
 char r;
 switch(a2)
 {
  case'+':      //此处由于加减几乎优先级一样，故放在一起
  case'-':
   if(a1=='('||a1=='#')
    r='<';
   else
    r='>';
   break;
  case'*':      //此处由于乘除优先级一样，故放在一起
  case'/':
   if(a1=='*'||a1=='/'||a1==')')
    r='>';
   else
    r='<';
   break;
  case'(':
   if(a1==')')
   {
    cout<<"括号匹配错误!"<<endl;
    exit(-1);
   }
   else
    r='<';
   break;
  case')':
   if(a1=='(')
    r='=';
   else if(a1=='#')
   {
    cout<<"error!没有左括号"<<endl;
    exit (-1);
   }
   else
    r='>';
   break;
  case'#':
   switch(a1)
   {
   case'#': 
    r='=';
     break;
   case'(':
    cout<<"error!没有右括号"<<endl;
    exit(-1);
   default:
    r='>';
   }//switch
   break;
 }//switch
 return r;
}//Precede

////////////////////////////////////////////////////////////////////////////////
                     /*判断是否为操作符的函数*/
bool In(char d)//判断c是否为七种运算符之一
{
 switch(d)
 {
 case'+':
 case'-':
 case'*':
 case'/':
 case'(':
 case')':
 case'#':
  return true;
 default:
  return false;
 }//switch
}
///////////////////////////////////////////////////////////////////////////////
                                /*以下为 运算函数*/

SElemType Operate( SElemType a,  SElemType theta, SElemType b )//Operate为进行二元运算的a theta b的函数
{
 char n=char(theta);//此处把double型强制转换成int型，虽然会造成精度缺失，但本身theta是一个符号，也算是整型
 switch(n)    //转换后相当于和符号匹配ACSII码
 {
 case'+':
  return a+b;
 case'-':
  return a-b;
 case'*':
  return a*b;
   default:
  if(b!=0)
   return a/b;
  else
  {
   cout<<"error!除数不能为零"<<endl;
   exit(-1);
  }
 }//switch
}
/////////////////////////////////////////////////////////////////////
                 /*以下为运算表达式的函数*/
SElemType EvaluateExpression()
{       //算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈
 SqStack OPTR,OPND;
 char  c;
 char Data[11];//定义此数组为了存放整数或小数
 SElemType a,b,d,e;
 InitStack(OPTR);//构造一个运算符栈
 InitStack(OPND);//构造一个运算数栈
 Push(OPTR,'#');//将#压入栈底
 c=getchar();
 GetTop(OPTR,e);
 while(c!='#'||e!='#')//栈顶不是#号且输入不是#号
 {
  if(In(c))//是符号则进栈
  {
   switch(Precede(e,c))
     {
   case'<':   //栈顶元素优先级低
    Push(OPTR,c);
    c=getchar();
    break;
   case'=':    //脱括号并接受下一字符
    Pop(OPTR,e);
    c=getchar();
    break;
   case'>':    //退栈并将运算结果入栈
    Pop(OPTR,e);
    Pop(OPND,b);
    Pop(OPND,a);
    Push(OPND,Operate(a,e,b));
    break;
   }//switch
  }
  else if(c>='0'&&c<='9'||c=='.')
  {
   int i=0;
   while(c>='0'&&c<='9'||c=='.')
   {
    Data[i]=c;
    i++;
    c=getchar();
   }
   Data[i]='/0';//数字没有存满,输入字符串结束符
   d=atof(Data);//此处是把数组里的数字，实际上是按字符串；转换为double类型，然后把浮点型数字入栈
   Push(OPND,d);//atof函数的形参是指针类型，故用数组名
  }
  else
  {
   cout<<"error!输入错误!"<<endl;
   exit(-1);
  }
  GetTop(OPTR,e);
 }//while
 GetTop(OPND,e);
 return e;
}//EvaluateExpression
////////////////////////////////////////////////////////////////////////////
                                  /*主函数main.cpp*/

int main()
{
 SElemType  result;
 cout<<"请输入表达式，以#号结束"<<endl;
 result=EvaluateExpression();
 cout<<"结果为:"<<result<<endl;
 return 0;
}