//#ifndef STACK_H
#define STACK_H
#include<iostream>
using namespace std;
template<typename T> class stack;
template <class T>
class stacknode
{
friend class stack<T>;
T data;
stacknode *next;
stacknode(const T& t)
{
data=t;
next=NULL;
}
};
template <class T>
class stack
{
private:
stacknode<T> *top;
public:
stack():top(NULL){}
~stack();
void push(const T&);
void pop();
bool Is_empty()
{
return top==NULL;
}
T Get_top()
{
return top->data;
}
};
#include"stack.cpp"
#endif
//stack.h,我在stack头文件中定义了栈模板类，下面是函数的实现
//stack.cpp
#include"stack.h"
template<class T> stack<T>::~stack()
{
stacknode<T> *p;
while(top)
{
p=top;
top=top->next;
delete p;
}
}
template<class T> void stack<T>::push (const T& t)
{
stacknode<T> *p=new stacknode<T>(t);
if(Is_empty())
top=p;
top->next=p;
top=p;
}
template<class T> void stack<T>::pop ()
{
if(Is_empty())
return;
stacknode<T> *p=top;
top=top->next;
delete p;
}

//表达式类头文件，分别用double和char类型的栈存储操作数和运算符。
#ifndef EXPRESSION_H
#define EXPRESSION_H
#include"stack.h"
using namespace std;
const SIZE=100;
class expression
{

private:
char express[SIZE];
stack<double> opnd;//操作数
stack<char> optr;//运算符
public:
expression();
~expression();
bool Is_operator(char);
char precede(char,char);
double operate(double,char,double);
double evaluate(char*);
};
#endif


//expression.cpp
#include"expression.h"
using namespace std;
expression::expression()
{
for(int i=0;i!=SIZE;++i)
express[i]='\0';
optr.push ('#');
}
expression::~expression ()
{
opnd.~stack ();
optr.~stack ();
}
bool expression::Is_operator (char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')
return true;
return false;
}
char expression::precede (char s1,char s2)
{
switch(s1)//条件的类型可以是整数类型，枚举类型，或者类类型（但该类需要有单一的转换到整数类型或（可以是字符类型，但不能是浮点类型、字符串、指针类型等），
{
case'+'://case 标号后必须为整型常量表达式
if(s2=='*'||s2=='/'||s2==')')
return '<';
else
return'>';
break;
case'-':
if(s2=='*'||s2=='/'||s2==')')
return '<';
else
return'>';
break;
case '*':
if(s2=='(')
return '<';
else return '>';
break;
case '/':
if(s2=='(')
return '<';
else return '>';
break;
case '(':
if(s2==')')
return '=';
else  
return '<';
break;
case ')':
return '>';
default:
if(s2=='#')
return '=';
else  
return '<';
break;
}
}
double expression::operate (double d1,char op,double d2)
{
if(op=='+')
return d1+d2;
else
if(op=='-')
return d1-d2;
else
if(op=='*')
return d1*d2;
else
return d1/d2;
}
double expression::evaluate (char* ch)
{


int i=0;
while(ch[i]!='#'||optr.Get_top ()!='#')
{
if(!Is_operator(ch[i]))
{
opnd.push (ch[i]);
++i;
}
else
switch(precede(optr.Get_top (),ch[i]))
{
case '<':
optr.push (ch[i]);
++i;
break;
case'=':
optr.pop ();
++i;
break;
case'>':
{
char opt=optr.Get_top ();
double a=opnd.Get_top ();
opnd.~stack ();
double b=opnd.Get_top ();
opnd.push (operate(a,opt,b));
}
break;
default:
break;
}
}
return opnd.Get_top ();
}
//main.cpp
#include"expression.h"
#include"stack.h"
using namespace std;
int main()
{
//double x;
char s[SIZE];
cout<<"请输入表达式"<<endl;
cin>>s;
expression ex;
cout<<"结果："<<endl;
cout<<ex.evaluate (s);
return 0;
}