#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(5);
  R.Push('@');
  int i=0,j=0;;
  char ch=s1[i];
  while(ch!='\0')
  {
	  if(ch==' ')
		  ch=s1[++i];
	  else if(ch=='(')
	  {
		  R.Push(ch);
		  ch=s1[++i];
	  }
	  else if(ch==')')
	  {
		  while(R.Peek()!='(')
			  s2[j++]=R.Pop();
		  R.Pop();
		  ch=s1[i++];
	  }
	  else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
	  {
		  char w=R.Peek();
		  while(Precedence(w)>=Precedence(ch))
		  {
			  s2[j++]=w;
			  R.Pop();w=R.Peek();
		  }
		  R.Push(ch);
		  ch=s1[++i];
	  }
	  else 
	  {
		  if((ch<'0'||ch>'9')&&ch!='.'){
		  cout<<"中綴表達式表示錯誤!"<<endl;
		  exit(1);
	  }
		 
	  while((ch<'0'&&ch>'9')||ch!='.'){
	  	  s2[j++]=ch;
			  ch=s1[++i];
		  }
		  s2[j++]='\0';
	  }
  }
  ch=R.Pop();
  while(ch!='@'){
	  if(ch=='('){
		  cerr<<"expression error!"<<endl;
		  exit(1);
	  }
	  else{
		  s2[j++]=ch;
		  ch=R.Pop();
	  }
  }
  s2[j++]='@';
  s2[j++]='\0';
}
double Compute(char *str){
	Stack<double> s(5);
double x,y;
	int i=0;
	while(str[i]){
		if(str[i]==' '){i++;continue;}
		switch(str[i]){
		case'+':
			x=s.Pop()+s.Pop();i++;
			break;
		case'-':
			x=s.Pop();
			x=s.Pop()-x;i++;
			break;
		case'*':
			x=s.Pop()*s.Pop();i++;
			break;
		case'/':
			x=s.Pop();
			if(x!=0.0)
				x=s.Pop()/x;
			else{
				cerr<<"Divide by 0!"<<endl;
				exit(1);
			}i++;
			break;
		default:
			x=0;
			while(str[i]>=48&&str[i]<=57){
				x=x*10+str[i]-48;i++;
		}
			if(str[i]=='.'){
				i++;y=0;
				float j=10.0;
				while(str[i]>=48&&str[i]<=57){
					y=y+(str[i]-48)/j;
					i++;j+=10;
				}
				x+=y;
			}
		}
		s.Push(x);
	}
		if(s.StackEmpty())
		{ cerr<<"Stack is empty!"<<endl;
		exit(1);}
		x=s.Pop();
		if(s.StackEmpty())
			return x;
		else{
			cerr<<"expression error!"<<endl;
			exit(1);
		}
}

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

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