运算.cpp

把中缀表达式转换成后缀表达式

#include<iostream>
#include "assert.h"
#include<cstring>
#include<cmath>
#define NULL 0
using namespace std;
//enum Boolean{true,false};
class stack
{
public:
	char *elmlist;
	char top;
	char msize;
	stack(int sz=20)
	{
		msize=sz;
		elmlist=new char[msize];
		assert(elmlist!=NULL);
		top=-1;
	}
	~stack()
	{delete []elmlist;}
	void push(char i);
	char pop();
	char gettop();
	void makeempty();
	int isfull(){return top==msize;}
	int isempty(){return top==-1;}

};

void stack::push(char i)
{
	assert(!isfull());
	top++;
	elmlist[top]=i;
}

char stack::pop()
{
	assert(!isempty());
		return elmlist[top--];
	
}
char stack::gettop()
{
	assert(!isempty());
	return elmlist[top];
}


void stack::makeempty()
{
	top=-1;
}

class list
{
public:
	int curr;
   list(const int LIST_SIZE);
   list(list &a);
   ~list();
   void clear();                    //清空顺序表
     
   void append(char value);          //在表尾增添一个新元素
   char remove(char i);               //当前下标curr位置的元素值作为返回值，并把该元素从顺序表删去
   char fetch(char i);               //返回nodelist[i]的值
   bool isinlist();               //若当前下标curr位置有值，则返回true
   bool isempty();                //当前表为空时。返回true
   char currvalue();                 //返回当前curr位置的元素值
   char length();                     //返回此顺序表的当前实际长度
   void prev();                      //将当前下标curr上移一格，即curr-1
   void disp();
private:
   char *nodelist;
   int msize;
   int curr_len;
};
list::list(const int LIST_SIZE)
{
	msize=LIST_SIZE;
	curr_len=0;
	nodelist=new char[LIST_SIZE];
}

list::list(list &a)
{
	nodelist=new char[a.msize];
	for(int i=0;i<a.curr_len;i++)
	nodelist[i]=a.nodelist[i];
	curr_len=a.curr_len;
	msize=a.msize;
}


list::~list()
{
	delete nodelist;
	curr_len=curr=0;
}
void list:: clear()
{
	curr_len=curr=0;
}
void list::append(char value)
{
	assert(curr_len<msize);
	nodelist[curr_len]=value;
	curr_len++;
}
char list::remove(char i)
{
	curr=i;
	assert((curr_len<msize)&&(curr>=0)&&(curr<curr_len));
	char temp=nodelist[curr];
	for(char k=curr;k<curr_len-1;k++)
		nodelist[k]=nodelist[k+1];
	curr_len--;
	return temp;
}
char list::length()
{
	if(curr_len=0)
		return NULL;
	
       return curr_len;
}
char list::fetch(char i)
{
	assert(i<curr_len);
	return nodelist[i];
}


char list:: currvalue()
{
	return nodelist[curr-1];
}
void list::prev()
{
	if (curr=1||curr>=curr_len)
		return;
	else
		curr=curr-1;
}

void list::disp()
{     curr=0;
	while(curr<curr_len-1)  
	{	cout<<nodelist[curr];
	    curr++;}

}




int priority(char op)
{
	   switch(op)
	{
	case '+':return 1;
	case '-': return 1;
	case '*':return 2;
	case '/': return 2;
	case '(':return 0;
	//case '#': return 0;
	default:
		return 0;
	}
}


list postfix(char *infix)
{
	stack s(40);
	list b(40);
	s.push('#');
    int i=0;
	do{
	    
		char k=infix[i];
		
		
		 if(k=='\0')
		 {	while (!s.isempty())
				b.append(s.pop());
			return b;
		 }
		else if(k=='+'||k=='-'||k=='*'||k=='/')
		{
			while(priority(k)<=priority(s.gettop()))
			{	b.append(s.gettop());
	     	    s.pop();
			}
			s.push(k);
			i++;
		}
		else if(k=='(')
		{	s.push(k);i++;}
		else if(k==')')
		{	while(s.gettop()!='(')
			{		
		         b.append(s.gettop());
			    s.pop();
			}
		s.pop();
		 i++;
		}
			else
			{	b.append(k);i++;}

		
	}while(1);
	
}



void main ()
{
	char a[20];
	cin.getline(a,20); 
	cout<<"中缀表达式是：";
    int i=0;
	while(a[i]!='\0')
		cout<<a[i++];
	cout<<endl;
	list b=postfix(a);
	cout<<"后缀表达式是：";
	b.disp();
	cout<<endl;


}