算术表达式求值演示编译成功.txt

数据结构

#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <strstrea.h>
const int SM = 20;
template <class ElemType>    //栈类声明
class Stack                                                                                                       
{
 public:
  //构造函数，初始化栈
    Stack(int ms);
  //析构函数，删除栈中的动态空间
    ~Stack();
  //清空栈
    void ClearStack(void);
  //检查栈是否为空
    bool StackEmpty(void);
  //读取栈顶元素
    ElemType PeeK(void);
  //向栈中插入元素
    void Push(const ElemType &item);
  //从栈中删除元素
    ElemType Pop(void);
  //检查栈是否已满
    bool StackFull(void);
 private:
     ElemType *m_stack;
     short m_top;
     short m_stackMaxSize;
};

//*栈成员函数的实现*
template<class ElemType>
Stack<ElemType>::Stack(int ms)
{2.
 m_stack = new ElemType[ms];
 if (!m_stack)
 {
  cerr<<"Memory allocation failure!";
  exit(1);
 }
 m_top = -1;
 m_stackMaxSize = ms;
}
//析构函数，删除栈中的动态空间
template<class ElemType>
Stack<ElemType>::~Stack(void)
{
 delete [] m_stack;
}
//清空栈
template<class ElemType>
void Stack<ElemType>::ClearStack(void)
{
 m_top = -1;
}
//检查栈是否为空
template<class ElemType>
bool Stack<ElemType>::StackEmpty(void)
{
 return (m_top == -1);
}
//读取栈顶元素
template<class ElemType>
ElemType Stack<ElemType>::PeeK(void)
{
 if (m_top == -1)
 {
  cerr<<"Stack is empty!"<<endl;
  exit(1);
 }
 return m_stack[m_top];
}
//向栈中插入元素
template<class ElemType>
void Stack<ElemType>::Push(const ElemType &item)
{
 if (m_top == m_stackMaxSize - 1)
 {
  cerr<<"Stack overflow!"<<endl;
  exit(1);
 }
 m_top++;
 m_stack[m_top] = item;
}
//从栈中删除元素
template<class ElemType>
ElemType Stack<ElemType>::Pop(void)
{
 if (m_top == -1)
 {
  cerr<<"Stack is empty!"<<endl;
  exit(1);
 }
 m_top--;
 return m_stack[m_top + 1];
}
//检查栈是否已满
template<class ElemType>
bool Stack<ElemType>::StackFull(void)
{
 return (m_top == m_stackMaxSize -1);
}


//求运算符优先级
int Precedence(char op)
{
 switch (op)
 {
  case '+':
  case '-':
   return 1; //定义加减运算的优先级为1
  case '*':
  case '/':
   return 2; //定义乘除运算的优先级为2
  case '(':
  case '=':
  default:
   return 0; //定义在栈中的左括号和栈底字符的优先级为0
 }
}
//将中缀表达式转换成后缀表达式
void Change(char *m_str1,char *m_str2)
{
 Stack<char> R(SM);   //定义用于暂存运算符的栈
 R.Push('=');    //给栈底放入‘='字符，它具有最低优先级0
 int i,j;    
 i = 0;      //用于指示扫描m_str1串中字符的位置，初值为0
 j = 0;      //用于指示m_str2串中待存字符的位置，初值为0
 char ch = m_str1[i];
 while (ch != '=')
 {
  if (ch == ' ')
  {
   ch = m_str1[++i];  //对于空格字符不做任何处理
  }
  else if (ch == '(')
  {      //对于左括号，直接进栈
   R.Push(ch);
   ch = m_str1[++i];
  }
  else if (ch == ')')
  {      //对于右括号，使括号内的仍停留在栈中的运算符依次
            //出栈并写入到m_str2中
   while (R.PeeK() != '(')
   {
    m_str2[j++] = R.Pop();
   }
   R.Pop();     //删除栈顶的左括号
   ch = m_str1[++i];
  }
  else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
  {      //对于四则运算符，使暂存在栈中的不低于ch优先级
        //的运算符依次出栈并写入到m_str2中
   char w = R.PeeK();
   while (Precedence(w) >= Precedence(ch))
   {     //Precedence()函数返回运算符形参的优先级
    m_str2[j++] = w;
    R.Pop();
    w = R.PeeK();
   }
   R.Push(ch);
   ch = m_str1[++i];
  }
  else
  {      //此处为数字或小数点字符的处理
   while (isdigit(ch) || ch == '.')
   {
    m_str2[j++] = ch;
    ch = m_str1[++i];
   }
   m_str2[j++] = ' ';   //被转换后的每个数值后放一个空格
  }
 }
 ch = R.Pop();
 while (ch != '=')
 {
  if (ch == '(')
  {
   cerr<<"表达式错误!"<<endl;
   exit(1);
  }
  else
  {
   m_str2[j++] = ch;
   ch = R.Pop();
  }
 }
 m_str2[j++] = '=';  //加入字符串结束符
 m_str2[j++] = '\0';
}
//计算后缀表达式值
float Compute(char *m_str2)
{
 Stack<float> S(SM);  //用S栈存储操作数和中间计算结果
 istrstream ins(m_str2); //把m_str2定义为输入字符串流对象ins
 char ch;    //用于输入字符
 float x;    //用于输入浮点数
 ins>>ch;    
 while (ch != '=')
 {
  switch (ch)
  {
   case '+':
    x = S.Pop() + S.Pop();
    break;
   case '-':
    x = S.Pop();
    x = S.Pop() - x;
    break;
   case '*':
    x = S.Pop() * S.Pop();
    break;
   case '/':
    x = S.Pop();
    if (x != 0.0) //判断除数是否为零
    {
     x = S.Pop() / x;
    }
    else 
    {
     cerr<<"除数不能为零!"<<endl;
     exit(1);
    }
    break;
   default:
    ins.putback(ch);
    ins>>x;
  }
  S.Push(x);
  ins>>ch;
 }
 if (!S.StackEmpty())
 {
  x = S.Pop();
  if (S.StackEmpty())   //如果栈中只有一个值那一定是结果
  {
   return x;
  }
  else
  {
   cerr<<"表达式错误!"<<endl;
   exit(1);
  }
 }
 else
 {
  cerr<<"表达式错误!"<<endl;
  exit(1);
 }
}
//判断是否为运算符
int IsOp(char ch)  
{
 switch (ch)
 {
  case '+':
  case '-':
  case '*':
  case '/':
   return 1;
   break;
  default:
   return 0;
   break;
 }
}
//提示信息显示
void TestMes(int n)
{
 switch (n)
 {
  case 0:
   cout<<"\n没有输入表达式..."<<endl;
   break;
  case 1:
   cout<<"\n表达式首字符不能是运算符..."<<endl;
   break;      
  case 2:
   cout<<"\n表达式中的运算符输入有误..."<<endl;
   break;
  case 3:
   cout<<"\n表达式中有非法字符..."<<endl;
   break;
  case 4:
   cout<<"\n没有以'='字符结束..."<<endl;
   break;
  case 5:
   cout<<"\n表达式括号不配对..."<<endl;
   break;
  case 6:
   cout<<"\n表达式计算中..."<<endl;
   break;
  default:
   break;
 }
}
//检查表达式是否有错
int Test(char *m_str1)
{
 char ch;   
 int i=0;
 int left = 0; //统计左括号
 int right = 0; //统计右括号
 ch = m_str1[i++];
 if (ch =='\0')  //没有输入了表达式
 {
  TestMes(0);
  return 0;
 }
 if (IsOp(ch))  //第一个是运算符
 {
  TestMes(1);
  return 0;
 }
 while (ch != '\0')
 {
   if (IsOp(ch) && IsOp(m_str1[i])) //运算符错误
   {
  TestMes(2);
  return 0;
   }
   if ((ch < '0') || (ch > '9'))  //有否非法字符
   {
    switch (ch)
    {   
    case '(':    //合法字符
     left++;
     break;
       case ')':
     right++;
     break;
    case ' ':
    case '+':
    case '-':
    case '*':
    case '/':
    case '=':
    case '.':
     break;
    default:   //非法字符
     TestMes(3);
     return 0;
     break;
    }
   }
   ch = m_str1[i++];
 }
 
 if (m_str1[i-2] != '=')  //结束符错误
 {
  TestMes(4);
  return 0;
 }
 if (left != right)   //括号问题
 {
  TestMes(5);
  return 0;
 }
    
 TestMes(6);  //表达式正确
 return 1;
}


//主程序
void main(void)
{
 char str1[50],str2[50];  
 char ch;
 cout<<"\n请输入以'='为结束符的算术表达式："<<endl;
 cin.getline(str1,sizeof(str1));
 
 while(!Test(str1))   //检查表达式是否正确
 {
  cout<<"\n请重新输入一个以'='为结束符的算术表达式："<<endl;
  cin.getline(str1,sizeof(str1));
 }
 Change(str1,str2);   //处理结果
 
 cout<<"\n求值结果为："<<str1<<Compute(str2)<<endl;
 getch();
}