中缀表达式.cpp

中缀表达式 实现简单

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/////////////模板类Stack的定义
template<class T>
class Stack
{ public:
     Stack(int n=50);      //建立一个空栈
     ~Stack();               //释放栈所占有的存储空间
     int StackEmpty()const;    //判断栈是否为空
     T gettop()const;           //获取栈顶元素
     void Push(const T  item);     //压栈函数
     T Pop();                       //将数字或运算符弹出栈
 private:
	 T *data;
	 int max,top;
};
////////////////////运算符类Oper的定义
class Oper
{ public:
      Oper( ) {};               
      Oper(char ch) ;            
	  int operator>=(Oper a)const;          //重载运算符>=
	  void Evaluate(Stack<double>& digit);        //计算表达式
  private:
	char sig;                    //字符变量
	int inputpre;               //读入优先级
	int stackpre;                //栈优先级
};
/////////////////模板类Stack的实现
template<class T>
Stack<T>::~Stack()
{delete  []data;}
template<class T>
Stack<T>::Stack(int n)              
{ data=new T[n];
  top=-1;                //初始化顺序栈
}
template<class T>
int Stack<T>::StackEmpty()const     
{  if(top==-1)
      return(1);            //栈是为空，则返回1
  return(0);
}
template<class T>
T  Stack<T>::gettop()const
{ if(top==-1)
    {  cout<<"Stack is empty!<<endl";       //报错函数   
    }
 return(data[top]);                      //获取栈顶元素
}
template<class T>                           
void Stack<T>::Push(const T item)
{  if(top==max-1)          
    {   cout<<"Stack is full!<<endl";      //报错函数  
    }
  top++;                               //指针变化并将元素压进栈  
  data[top]=item;        
}
template<class T>
T  Stack<T>::Pop()                 
{  if(top==-1)
    {  cout<<"Pop an empty stack!"<<endl;    //报错函数    
    }
   T x;
   x=data[top--];                //栈顶元素赋给x 
   //return  data[top--];  
    return x;                //返回栈顶元素 
}
////////////////////运算符类Oper的实现
Oper::Oper(char ch)             //运算符优先级规定函数 
{  sig=ch;
   switch(sig)
   { case'+':
     case'-':inputpre=1;
	         stackpre=1;
             break;
    case'*':
    case'/':inputpre=2;
	        stackpre=2;
            break;
    case'(':inputpre=3;            //左括号的读入优先级最高
	        stackpre=-1;               //左括号的栈优先级最低
            break;
    case')':inputpre=0;              //右括号的读入优先级最高
	        stackpre=0;
            break;
   }
}
int Oper:: operator>=(Oper a)const  
{return(stackpre>=a.inputpre);      //比较操作符栈的栈顶元素栈优先级和当前操作符的读入优先级
}
void  Oper::Evaluate(Stack<double>& digit)    //计算表达式函数
{   double digit1=digit.Pop();        //数据出栈
    double digit2=digit.Pop();        //数据出栈
    switch(sig)     
	{ case'+':digit.Push(digit2+digit1);      //将两数据的和入数据栈
	          break;
      case'-':digit.Push(digit2-digit1);        //将两数据的差入数据栈 
		      break;
      case'*':digit.Push(digit2*digit1);         //将两数据的积数据入栈
		      break;
      case'/':digit.Push(digit2/digit1);        //将两数据的商入数据栈  
		      break;
	}
}
/////////////////判断将要进栈元素的类别
int isoptr(char ch)                          
{  if(ch=='+'||ch=='*'||ch=='/'||ch=='('||ch=='-')
     return(1);
   else
     return(0);
}
/////////////////实现中缀表达式的计算并输出其结果
void Infix(char  *str)
{   char  ch,num[20];          //num[]用于保存字符串中的数字
    int i,k, n=strlen(str);     //计算n以便在构造函数里申请足够的空间
    double digit;
    Oper  optr1;         //定义字符类的对象       
    Stack<double>  digitS(n);    //定义模板类的对象
	Stack<Oper>   OptrS(n);       //定义模板类的对象
    k=0;ch=str[k];                //给字符赋值
   while(ch!='=')
   { if(ch>='0'&&ch<='9'||ch=='.')                //如果是数字字符或小数点
       { for(i=0;ch>='0'&&ch<='9'||ch=='.';i++)   //连续读入一个数字字符串到数组
          {   num[i]=ch;
              k++;
              ch=str[k];
           }
        num[i]='\0';
        digit=atof(num);           //将数字字符串转换为数字
        digitS.Push(digit);       //将数字进栈
	 }
   else if(isoptr(ch))                      //如果是运算符或左括号
	 { optr1=Oper(ch);                      //定其优先级
       while(! OptrS.StackEmpty()&&OptrS.gettop()>=optr1)   //操作符栈非空且前一操作符的栈优先级大于当前操作符的读入优先级
          OptrS.Pop().Evaluate(digitS);          //实现当前数据和操作的运算
       OptrS.Push(optr1);                     //将运算符或左括号信息压进操作符栈
       k++;
       ch=str[k];
	 }
    else if(ch==')')
	{   optr1=Oper(ch);        //判断操作符的优先级
        while( !OptrS.StackEmpty()&&OptrS.gettop()>=optr1)  
           OptrS.Pop().Evaluate(digitS);
        OptrS.Pop();                            //将栈中的左括号弹出
        k++;
        ch=str[k];
	}
   }
   while( !OptrS.StackEmpty())               //操作符栈非空，执行数据栈中，最后两数的计算
      OptrS.Pop().Evaluate(digitS);                  
   digit=digitS.Pop();                         //获取数据栈中的最后一个元素，并记作计算结果
   cout<<"计算结果："<<digit<<endl;            //输出结果
}
///////////////////////输出该操作系统的界面及提示语
int print()           
{ int flag;                     //设置标兵，实现中缀表达式的多次计算
  cout<<endl<<endl<<"*******************************************************************"<<endl;
  cout<<"                欢迎您,中缀表达式计算系统            "<<endl;
  cout<<"   进入请按1,否则请按0"<<endl;
  cin>>flag;
  return flag;
 }

////////////////////主函数
void main()
{   char str[50];            //保存用户所输中缀表达式
    for( ; print();)        //实现中缀表达式的多次计算
	{   cout<<"请输入表达式（再输入“=”便可得到其结果）:"<<endl;
	    
		gets(str);             //读取中缀表达式
        Infix(str);         //计算中缀表达式并输出结果
	 }
}