#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<conio.h>
#include<process.h>
#include <ctype.h>
#include<strstrea.h>
#include<string.h>
template<class ElemType>
class Stack{
public:
	ElemType *stack;
    int top;
	int StackMaxSize;
	public:
 Stack(int ms);
 void Push(ElemType item);
  ElemType Pop(); 
 ElemType Peek();
 bool StackEmpty();
 ~Stack();
void AllotStack();
};
template<class ElemType>
Stack<ElemType>::Stack(int ms){
	StackMaxSize=ms;
		stack=new ElemType[ms];
	if(!stack){
		cerr<<"Memory allocation failure!";
		exit(1);
	}
	top=-1;
}
template<class ElemType>
void Stack<ElemType>::Push(ElemType item){
	if(top==StackMaxSize-1)AllotStack();
	top++;
	stack[top]=item;
}
template<class ElemType>
ElemType Stack<ElemType>::Pop(){
if(top==-1){
		cerr<<"Stack is empty!"<<endl;
		exit(1);
	}
	top--;
	return stack[top+1];
}
template<class ElemType>
ElemType Stack<ElemType>::Peek(){
	if(top==-1){
		cerr<<"Stack is empty!"<<endl;
		exit(1);
	}
	return stack[top];
}
template<class ElemType>
bool Stack<ElemType>::StackEmpty(){
		return top==-1;
}
template<class ElemType>
Stack<ElemType>::~Stack(){
	delete[]stack;
	stack=0;
	top=-1;
	StackMaxSize=0;
}
template<class ElemType>
void Stack<ElemType>::AllotStack(){
	ElemType *p=new ElemType[2*StackMaxSize];
	StackMaxSize*=2;
	for(int i=0;i<=top;i++)
		p[i]=stack[i];
	delete[]stack;
	stack=p;
}
int Precedence(char op)
{
	switch(op){
	case'+':
	case'-':
		return 1;
	case'*':
	case'/':
		return 2;
	case'(':
	case'@':
	default:
		return 0;
	}
}
void Change(char *s1,char *s2){
	Stack<char> R(30);
	 R.Push('@');
  int i=0,j=0;;
  char ch=s1[i];
  while(ch!='@')
  {
	  if(ch==' ')
		  ch=s1[++i];
	  else if(ch=='(')
	  {
		  R.Push(ch);
		  ch=s1[++i];
	  }
	  else if(ch==')')
	  {
		  while(R.Peek()!='('){
			  s2[j++]=R.Peek(); 
		  R.Pop();
	  }
	  R.Pop();
		  ch=s1[i++];
	  }
	  else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
	  {
		  if(R.Peek()=='@'){
			  R.Push(ch);ch=s1[++i];}
		  else
		  {
		  char w=R.Peek();
		  while(Precedence(w)>=Precedence(ch))
		  {
			  s2[j++]=w;
			  R.Pop();w=R.Peek();
		  }
		  R.Push(ch);
		  ch=s1[++i];
	  }
	  }
	  else 
	  {
			while(isdigit(ch)||ch=='.')
			{
				s2[j++]=ch;
				ch=s1[++i];
			}
			s2[j++]=' ';
		}
	}
	
	ch=R.Peek();
	R.Pop();
	while(ch!='@')
	{
		if(ch=='(')
		{
			cerr<<"表達式錯誤"<<endl;
			exit(1);
		}
		else
		{
			s2[j++]=ch;
			ch=R.Peek();
			R.Pop();
		}
	}
	s2[j++]='@';
	s2[j++]='\0';
	
}

double Compute(char *str){
	
	Stack<double> b1(30);
	istrstream ins(str);
	char ch;
double x;
ins>>ch;
	while(ch!='@')
	{
		switch(ch)
		{
		case'+':
			x=b1.Peek();
			b1.Pop();
			x=x+b1.Peek();
			b1.Pop();
			break;
		case'-':
			x=b1.Peek();
			b1.Pop();
			x=b1.Peek()-x;
			b1.Pop();
			break;
		case '/':
			x=b1.Peek();
			b1.Pop();
			if(x!=0.0)
			{
				x=b1.Peek()/x;
				b1.Pop();
			}
			else
			{
				cerr<<"Divided by 0!"<<endl;
				exit(1);
			}
			break;
		case '*':
			x=b1.Peek();
			b1.Pop();
			x=x*b1.Peek();
			b1.Pop();
			break;
		default:
			ins.putback(ch);
			ins>>x;
		}
		b1.Push(x);
		ins>>ch;
	}
	if(!b1.StackEmpty())
	{
		x=b1.Peek();
		b1.Pop();
		if(b1.StackEmpty())
			return x;
		else
		{
			cerr<<"expression is error!"<<endl;
			exit(1);
		}
	}
	else
	{
		cerr<<"stack is empty!"<<endl;
		exit(1);
	}
}

void opera2()
{
	char a[30];
	char b[30];
	cout<<"輸入一個以@字符為結束的中綴算術表達式:"<<endl;
	cin.getline(a,sizeof(a));
		cin.getline(a,sizeof(a));

	Change(a,b);
	cout<<"對應的后綴算術表達式為:"<<endl;
	cout<<b<<endl;
	cout<<"求值得結果為:"<<Compute(b)<<endl;
}