03.cpp

编译原理实验中有关中缀表达式转后缀表达式输出的程序代码.

#ifndef _STACK_H
#define _STACK_H

#include <iostream.h>

template <class T>
class Stack
{
public:
virtual bool IsEmpty()const=0;
virtual bool IsFull()const=0;
virtual bool Push(T x)=0;
virtual bool Pop()=0;
virtual bool Top(T &x)const=0;
virtual bool Clear()=0;
};

#endif

#ifndef   _SEQSTACK_H
#define   _SEQSTACK_H
#include "Stack.h"

template <class T>
class SeqStack;

template <class T>
class Node
{
Node(T a, Node<T>* p)
{
   Data = a;
   Next = p   ;
} 
Node()
{
   Next = NULL;
} 
private:
T Data;
Node<T>* Next;
friend class SeqStack<T>;
};


template <class T>
class SeqStack:public Stack<T>
{
public:
SeqStack(int maxsize);
~SeqStack();
bool IsEmpty()const;
bool IsFull()const;
bool Push(T x);
bool Pop();
bool Top(T &x)const;
bool Clear(); 
private:
int Maxsize;
int size;
Node<T>* top;
};

template <class T>
SeqStack<T>::SeqStack(int maxsize)
{
Maxsize = maxsize;
top = new Node<T>;
size = 0;
}

template <class T>
SeqStack<T>::~SeqStack()
{
Clear();
}

template <class T>
bool SeqStack<T>::IsEmpty()const
{
return size == 0;
}

template <class T>
bool SeqStack<T>::IsFull()const
{
return size == Maxsize;
}

template <class T>
bool SeqStack<T>::Pop()
{
if(IsEmpty())
{
   cerr <<"The SeqStack is empty! "<<endl;
   return false;
}
Node<T>*p = top;
top = top->Next;
delete p;
size --;
return true;
}

template <class T>
bool SeqStack<T>::Push(T x)
{
if (IsFull()) 
{
   cerr <<"The SeqStack is full!"<<endl;
   return false;
} 
Node<T>* p = new Node<T>(x,0);
p->Next = top;
top = p;
size++;
return true;
}

template <class T>
bool SeqStack<T>::Top(T &x)const
{
if (IsEmpty())
{
   cerr <<"The SeqStack is empty! "<<endl;
   x = 0;
   return false;
}

x = top->Data;
return true;
}

template <class T>
bool SeqStack<T>::Clear()
{
Node<T>* p = top;
while (p)
{
   top = top->Next;
   delete p;
   p = top;
}
delete p;
return true;
}


#endif

#ifndef _CALCULATOR_H
#define _CALCULATOR_H

#include "SeqStack.h"
#include <iostream.h>

class Calcualtor
{
public:
Calcualtor(int size1, int size2):Operator(size1),Operand(size2)
{
   Operator.Push( '#' );
}

~Calcualtor()
{
   Operator.Clear();
   Operand.Clear();
}

void Run();//从输入流读入字符，做相应的运算，输出结果；

/*void Clear()
{
   S.Clear();
}*/


private:
SeqStack <double> Operand;
SeqStack <char> Operator;
//处理操作数堆栈
void PushOperand( double );
bool GetOperand( double&, double&);
//进行运算
void DoOperator( char );//根据相应操作符做相应的操作
//分别返回栈内和栈外优先级
int InPri( char );
int OutPri( char );
};

void Calcualtor::PushOperand(double x)
{
Operand.Push(x);
}

bool Calcualtor::GetOperand(double &a, double &b)
{
if (!Operand.Top(a))
{
   cerr << "An error occur!" << endl;
   return false;
} 
Operand.Pop(); 

if (!Operand.Top(b))
{
   cerr << "An error occur!" << endl;
   return false;
} 
Operand.Pop();

return true;
}

void Calcualtor::DoOperator(char opertor)
{
switch(opertor) 
{
case '+':
   {
    double a, b;
    double temp;
    GetOperand(a,b);
    temp = a + b;
    PushOperand(temp);
   }
   return;
case '-':
   {
    double a, b;
    double temp;
    GetOperand(a,b);
    temp = b - a;
    PushOperand(temp);
   
   }
   return;
case '*':
   {
    double a, b;
    double temp;
    GetOperand(a,b);
    temp = b * a;
    PushOperand(temp);
   
   }
   return;
case '/':
   {
    double a, b;
    double temp;
    GetOperand(a,b);
    temp = b / a;
    PushOperand(temp);
   }
   return;
default: return;
}
}

void Calcualtor::Run()//扫描表达式
{
char symbol;
double newOperand;
while (cin >> symbol)
{
   switch(symbol) 
   {
   case '+':
    {
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) >= OutPri(symbol)) 
     {
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);
     }
     Operator.Push('+');
     break;
    }
   case '-':
    {
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) >= OutPri(symbol)) 
     {
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);
     }
     Operator.Push('-');
     break;
    } 
   case '*':
    {
    
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) >= OutPri(symbol)) 
     {
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);
     }
     Operator.Push('*');
     break;
    
    } 

   case '/':
    {
    
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) >= OutPri(symbol)) 
     {
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);
     }
     Operator.Push('/');
     break;
    
    }
   case '(':
    {
     Operator.Push('(');
     break;
    }
   
   case ')':
    {
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) != 1) 
     { 
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);     
     }
     Operator.Pop();
     break;
    }
   case '#':
    {
     char tchar;
     Operator.Top( tchar );
     while (InPri(tchar) != 0) 
     {
      DoOperator(tchar);
      Operator.Pop();
      Operator.Top(tchar);
     }
   
     double result;
     Operand.Top(result);
     cout << "The result is :" << result << endl;
     return;
    }
   default://处理操作数
    {
     cin.putback(symbol);
     cin >> newOperand;
     PushOperand(newOperand);
    }  
   }
}

}

int Calcualtor::InPri(char c)
{
switch(c)
{
case '+':
   return 3;
case '-':
   return 3;
case '*':
   return 5;
case '/':
   return 5;
case '(':
   return 1;
case ')':
   return 7;
case '#':
   return 0;
default:
   return -1;
}
}

int Calcualtor::OutPri(char c)
{
switch(c)
{
case '+':
   return 2;
case '-':
   return 2;
case '*':
   return 4;
case '/':
   return 4;
case '(':
   return 7;
case ')':
   return 1;
case '#':
   return 0;
default:
   return -1;
}
}

#endif

#include <iostream>
#include "SeqStack.h"
#include "Calculator.h"

void main()
{

   Calcualtor cal(10,10);
     cal.Run();

}