中缀表达式转换成后缀表达式.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include <iostream>
#include <assert.h>
#include <string.h>
//#include <stack>
using namespace std;
//**********************************
template <class Type> class Stack;

template <class Type> class StackNode {
	friend class Stack<Type>;
private:
	Type data;
	StackNode<Type> *link;
	StackNode(Type d = 0, StackNode<Type> *l=NULL):data(d),link(l){}
};
//-------------------------------------------------------------------
template<class Type> class Stack {
	StackNode<Type> *top;
public:
	Stack():top(NULL){} //构造函数
	~Stack();
	void Push( const Type& item);
	Type Pop();
	Type GetTop();
	void MakeEmpty();
	int IsEmpty()const{ return top==NULL; }
	void print();
	void removetop();
};

template<class Type> Stack<Type>::~Stack() {
	StackNode<Type> *p;
	while(top!=NULL)
	{
		p = top;
		top = top->link;
		delete p;
	}
}

template<class Type> void Stack<Type>::MakeEmpty() {
	StackNode<Type> *p;
	while(top!=NULL)
	{
		p = top;
		top = top->link;
		delete p;
	}
}

template<class Type> void Stack<Type>::Push(const Type& item) {
	top = new StackNode<Type>(item, top);
}

template<class Type> void Stack<Type>::removetop() {
	  assert( !IsEmpty() );
	  StackNode<Type> *p;
	  p = top;
	  top = top->link;
	  delete p;
}

template<class Type> Type Stack<Type>::Pop() {
	assert( !IsEmpty() );
	StackNode<Type> *p = top;
	Type retvalue = p->data;
	top = top->link;
	delete p;
	return retvalue;
}

template<class Type> Type Stack<Type>::GetTop() {
	assert( !IsEmpty() );
	return top->data;
}

template<class Type> void Stack<Type>::print() {
	cout<<"当前的 Stack 为："<<endl;
	StackNode<Type> *p = top;
	while (p!=NULL)
	{
		cout<<p->data<<endl;
		p = p->link;
	}
}
//----------------------------------------
int order[] = {1, 1, 2, 2, 0,-1};

int getorder(char opt) {
	switch(opt)
	{
	case '#':
		return order[5];
	case '+':
		return order[0];
	case '-':
		return order[1];
	case '*':
		return order[2];
	case '/':
		return order[3];
	case '=':
		return order[4];
	default:
		printf("\nKnown operator \'%c\'.\n", opt);
		exit(-1);
	}
}

int compute(int t1, int t2, char opt) {
	switch(opt)
	{
	case '+':
		return t1+t2;
	case '-':
		return t1-t2;
	case '*':
		return t1*t2;
	case '/':
		if (t2 == 0)
		{
			printf("\nZero divided!\n");
			exit(0);
		}
		return t1/t2;
	default:
		printf("\nKnown operator \'%c\'.\n", opt);
		exit(-1);
	}
}

//***************************************************
void main() {

	Stack<int> stack;
	int x=0;
	cout<<"请输入要 Push 的 x:\n";
	cin>>x;
	stack.Push(x);
	cin>>x;
	stack.Push(x);
	stack.print();
	cout<<"Top is:"<<stack.GetTop()<<endl;
	cout<<"退出Top:\n";
	stack.removetop();	
	stack.print();
	cout<<"清空：\n";
	stack.MakeEmpty();
	stack.print();

//-------------------------------------------------------------------------

	Stack<int> s1;
	Stack<char> s2;
	char exp[] = "1+2*4=";
	char *p = exp;

	Stack<string> ss;
	//s1.MakeEmpty();
	//s2.MakeEmpty();

	s2.Push('#');
	while (*p)
	{
		if (isdigit(*p))
		{
			s1.Push(*p-'0');
			ss.Push( string(p, 1) );
			p++;
		}
		else
		{
			if (s2.IsEmpty())
			{
				s2.Push(*p);
				p++;
			}
			else
			{
				char topch = s2.GetTop();
				if (getorder(*p) > getorder(topch))
				{
					s2.Push(*p);
					p++;
				}
				else
				{
					int t1, t2;
					string ts1, ts2;
					t2 = s1.Pop();
					ts2 = ss.Pop();		
					t1 = s1.Pop();	
					ts1 = ss.Pop();	

					s2.removetop();
					s1.Push(compute(t1, t2, topch));
					string opts(1, topch);
					string s(ts1);		s+=ts2;
					s+=opts;        ss.Push(s);
				}
			}
		}
	}
	printf("\n%s%d", exp, s1.GetTop());
	printf("\nSuffix exp: %s\n", ss.GetTop().c_str());

}