#include "stack.h"
#include <string>
#include <vector>
using namespace std;

void RPN(string,char *);
int procecn( char);
void Count( char *);

int main()
{
string exp;
char answerexp[255];
cout<< "NOTE: Enter # for infix expression to stop.\n";
for(;;)
{
cout<< "\nInfix Expression? ";
getline(cin,exp,'\n');
if( exp == "#") break;
RPN(exp,answerexp);
cout<< "RPN Expression is " << answerexp <<endl;
Count(answerexp);

}
}

int procecn(vector<char> ch)
{

switch(ch[0])
{
case '+':case '-':
return 2;
case '*':case '/':
return 3;
case '<':case '>':
if(*(ch.end()-1) == '<'||*(ch.end()-1) == '>')
return 1;
default:
return 0;
}
}

void RPN(string exp,char * answerexp)
{

Stack<char,128> s;
int j=0,i=0;
vector<char> ch,temp;
s.push('@');

while(i< exp.length())
{
ch.push_back(exp[i]);
if( ch[0] == ' ')
i++;
else if ( ch[0] == '(')
{
s.push( ch[0] );
i++;
}
else if ( ch[0] == ')')
{
while( s.gettop() != '(')
{
answerexp[j++] = s.gettop();
s.pop();
}
s.pop();
i++;
}
else if( ch[0] == '*'|| ch[0] =='/' ||
ch[0] == '-' || ch[0] == '+'|| ch[0] == '<'|| ch[0] == '>')
{
if(exp[i+1] == '<')
{
i++;
ch.push_back('<');
}
else if(exp[i+1] == '>')
{
i++;
ch.push_back('>');
}
temp.push_back(s.gettop());
if( procecn(temp) >= procecn( ch) )
{

if(s.gettop() == '<')
{
while(s.gettop() == '<')
{
answerexp[j++] = s.gettop();
s.pop();
}
}
else if( s.gettop() =='>')
{
while(s.gettop() == '>')
{
answerexp[j++] = s.gettop();
s.pop();
}
}

else{
answerexp[ j++ ] = s.gettop();
s.pop();
}
}
temp.clear();
vector<char>::iterator it = ch.begin();
for(; it != ch.end(); ++it)
s.push(*it);

i++;
}
else{
while( exp[i] >= '0' && exp[i] <= '9')
{
answerexp[j++] = exp[i];
i++;
}
}
answerexp[j++] = ' ';
ch.clear();
}

while(s.gettop()!= '@')
{
if( s.gettop() == '(')
{
cout << " Error in infix expression \n";
exit(-1);
}
else{
answerexp[j++] = s.gettop();
s.pop();
}
}
answerexp[j] = '\0';

s.pop();
}

void Count(char *answerexp)
{

int sum = 0,num1,num2,i = 0;
char ch;
Stack<int,128> s;
while ( answerexp[i] != '\0')
{
ch = answerexp[i];
switch(ch)
{
case '+':
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( num1+num2);
i++;
break;
case '-':
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( num2-num1);
i++;
break;
case '*':
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( num1*num2);
i++;
break;
case '/':
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( num2/num1);
i++;
break;
case '<':
if( answerexp[i+1] == '<')
{
i++;
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( (num2<<num1));
}
i++;
break;
case '>':
if( answerexp[i+1] =='>')
{
i++;
num1 = s.gettop();
s.pop();
num2 = s.gettop();
s.pop();
s.push( (num2>>num1) );
}
i++;
break;
case ' ': i++; break;
default:
while(ch >= '0' && ch <= '9')
{
sum = sum*10+(ch-'0');
i++;
ch = answerexp[i];
}
s.push(sum);
sum = 0;
break;
}
}
cout<<"the result is "<<s.gettop()<<endl;
s.pop();
}

//stack.h
#include "exception.h"

#ifndef STACK
#define STACK

template<typename T,int stack_capacity>
class Stack{
public:
Stack():mytop(-1){ myarray = new T[stack_capacity];}
~Stack(){ delete []myarray;}
bool empty(){ return mytop == -1;}
bool full() { return mytop == stack_capacity-1;}
void push(const T&);
void pop();
T gettop();
void display(ostream &);
private:
T *myarray;
int mytop;
};

template<typename T,int stack_capacity>
void Stack<T,stack_capacity>::push(const T &value){
if( full())
throw pushOnFull<T>(value);
else
myarray[++mytop] = value;
}

template<typename T,int stack_capacity>
void Stack<T,stack_capacity>::pop(){
if( empty())
throw popOnEmpty<T>();
else
mytop--;
}

template<typename T,int stack_capacity>
T Stack<T,stack_capacity>::gettop(){
if(empty())
throw popOnEmpty<T>();
else
return myarray[mytop];
}

template<typename T,int stack_capacity>
void Stack<T,stack_capacity>::display( ostream &os)
{
for( int i=0;i<= mytop;i++)
os<< myarray[i] <<" ";
}
#endif

//exception.h
#include <iostream>
using namespace std;

template<typename T>class Excp{
public:
virtual void print(){
cout<< "An exception has occurred"<<endl;
}

};

template<typename T>class stackExcp:public Excp<T>{
};

template<typename T>class pushOnFull:public stackExcp<T>{
public:
pushOnFull(T i):_value(i){}
int value(){ return _value;}

virtual void print()
{
cerr <<"trying to push the value "<<_value<<" on a full stack\n";
}
private:
T _value;
};

template<typename T>class popOnEmpty:public stackExcp<T>{
public:
virtual void print()
{
cerr<<"trying to pop"<<endl;
}
};

这么长.......................

谢谢大家了！