常见的方法：
（1）采用后缀表达式计算；（2）采用两个堆栈实现计算；
（3）通过表达式建立二叉树，再通过后序遍历计算。
三种方法的共同点就是对于以字符串为原始形式的表达式，要提取每个表达式的元素，这里包括数据和运算符，我写的代码里，以
一个单链表，把各个元素提取了出来，用链表连接起来，这样无论采用哪种方式进行计算得心应手。实现方法：定义的链表结点包括一下几个元素：int etype;结点的类型，即是数据结点还是运算符结点，还有一个union类型，用于存放数据或者运算符，再加上一个链接指针link，核心代码如下：
首先是类及相关结构的定义：
//////////////////////////////////////////////////
//ExpNode结构 表达式元素的结点
//这个结点要么是数据此时etype=0,
//要么是运算符,此时etyp=1;
//////////////////////////////////////////////////
struct ExpNode
{
int etype; //类型,0:数据,1:运算符
union content //内容的联合体
{
double data; //数据
char op; //运算符
} info;
ExpNode* link; //链接指针
ExpNode() //默认构造函数
{etype=0;info.data=0;link=NULL;};
};
///////////////////////////////////ExpNode结构结束
//////////////////////////////////////////////////
//Expression类 表达式类的实现
//////////////////////////////////////////////////
class Expression
{
private:
char* s; //表达式字符串
int n; //表达式的长度(不含’\0′的长度)
ExpNode* Exp; //表达式元素链表头指针(带附加头结点的链表)
public:
Expression() //默认构造函数
{s=NULL;n=0;};
Expression(char* e);//带参数的构造函数
~Expression() //析构函数
{if(s!=NULL)delete [] s;};
void Analyzer(); //当前表达式的字符串
int leftp(char o); //得到左优先级
int rightp(char o); //得到右优先级
double Caculate1(); //利用数据栈和符号栈计算当前表达式的值
BinTreeNode*
CreExpBinTree();//通过当前的表达式来创建对应的表达式二叉树
void Display(); //显示Exp[]数组里的内容
friend ostream&
operator<<( //友元重载<<输出运算符
ostream& os,Expression& E);
};
////////////////////////////Expression类的实现结束
通过简单的词法分析，提取表达式字符串中元素，并建立链表：
//////////////////////////////////////////////////
//Analyzer()公有成员函数
//词法分析器,提取表达式中运算符和数据放入Exp链表
//////////////////////////////////////////////////
void Expression::Analyzer()
{
double val=0; //存放提取的数据元素的值
int f=0; //标记是整数还是小数部分0:整数,1:小数
int e=-1; //计算小数部分时用到的指数
int count=0; //表达式元素个数计数器
ExpNode* rear=Exp; //表达式结点链表尾指针
ExpNode* ptr; //新建结点的指针
for(int i=0;i {
if(isdigit(s[i])) //如果是数字
{
if(f==0) //如果是整数部分
val=val*10+(int(s[i])-48);
else //如果是小数部分
{
val=val+
(int(s[i])-48)*pow(10,e);
e–; //指数减1继续下次运算
};
if(!isdigit(s[i+1])
&&s[i+1]!=’.') //如果当前的字符的下个字符是运算符
{
ptr=new ExpNode; //新建一个数据结点
ptr->etype=0;
ptr->info.data=val;
val=0;
rear->link=ptr; //新的尾结点
rear=ptr;
};
}
else if(s[i]==’.') //如果遇到是的小数点’.’
f=1;
else //如果是运算符(包括括号)
{
f=0;
ptr=new ExpNode; //新建一个运算符结点
ptr->etype=1;
ptr->info.op=s[i];
rear->link=ptr;
rear=ptr;
};
};
};
////////////////////////////////Analyzer()函数结束
通过两个堆栈来实现对已经建立好的单链表表达式进行计算：
//////////////////////////////////////////////////
//Caculate1()公有成员函数
//利用数据堆栈和符号堆栈来实现表达式的计算
//所有的计算都是基于已经创建好的表达式链表Exp
//////////////////////////////////////////////////
double Expression::Caculate1()
{
ExpNode* ptr=Exp->link; //表达式结点游标指针
LinkedStack Opstk; //运算符栈
LinkedStack Datastk; //操作数堆栈
Opstk.Push(‘#’);
while(ptr!=NULL) //遍历表达式的每个元素
{
if(ptr->etype==0) //如果从表达式链表中取出的是数据
{
Datastk.Push(
ptr->info.data); //送入操作数堆栈
ptr=ptr->link; //取下个表达式结点
}
else //如果取出的是运算符
{
char lop;
Opstk.getTop(lop); //从堆栈顶部取出左运算符
char rop=ptr->info.op;//从表达式中取出当前的运算符
if(leftp(lop)