c++实现字符串表达式求值（逆波兰式）_c++字符串表达式资源-CSDN文库

共11个文件

h：4个

cpp：4个

doc：2个

逆波兰式

5星 · 超过95%的资源需积分: 43 193 浏览量 2011-04-23 17:53:27 上传评论 11 收藏 55KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

CalcStrExpression.rar （11个子文件）

CalcStrExpression

main.cpp 557B

ExpTree.cpp 1KB

ExpAlgorithm.h 2KB

ExpAlgorithm.cpp 6KB

OperatorStack.h 517B

ExpTree.h 1KB

CalcStrExpression.dsp 5KB

OperatorStack.cpp 2KB

SimpleStack.h 3KB

逆波兰式表达式.doc 43KB

二叉表达式树.doc 83KB

二叉表达式树

http://blog.csdn.net/timercrack/archive/2007/11/08/1874767.aspx

终于到谈到树了，可以说数据结构最精彩的算法都出自这里(但不是最复杂的，后面还有图..)。接下

来的 2 篇文章会介绍有关树的一些操作和应用。

树的两个基本用途，可以用物质和精神来比喻。

一个用途是做为数据储存，储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储

存载体上（内存、磁盘）储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子

树，树可以采取各种方法来储存——多叉链表、左孩子－右兄弟二叉链表、广义表、多维数组。由于操

作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。

一个用途是做为逻辑判断，此时会常常听到一个名词——判定树。最常用的结构是二叉树(见下文)，

一个孩子代表 true，一个孩子代表 false。关于多叉判定树，有个例子是求 8 皇后的全部解——这个连高

斯都算错了（一共是 92 组解，高斯最开始说 76 组解），我们比不上高斯，但是我们会让 computer 代

劳。

就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能

区分是做为储存来用还是做为判断来用，比如搜索树，既储存了数据，还蕴涵着判断，这在后续的文章

会提到。

和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交

道——看看你电脑里的文件夹吧^_^

首先要介绍的是树形结构中最基础、最常用的所谓二叉树。二叉树可以说是人们假想的一个模型，

因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的是不同的两棵

二叉树树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义。二叉树有多种存储方式，下面

只讲解链式结构。看各种讲数据结构的书，你会发现一个有趣的现象：在二叉树这里，基本操作有计算

树高、寻找节点以及各种遍历，但就是没有插入、删除操作。那树是怎么建立起来的？其实这很好理解，

对于非线性的树形结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应

用中，才会有插入删除操作。

与之前的文章一样，这里不讨论各种基本操作，而是讲一些实际应用。我发现这样更有利于加深对

数据结构的理解。这里讲书上的例子：二叉表达式树。但书上一个具体算法都没有给出，倒是随书光盘

里给出了一个中缀表达式建树的演示，我就根据它编写了一个完整的表达式树类，下面以它来介绍二叉

树的一些典型操作。包括：输入任意形式的表达式建立一棵树，表达式树的求值以及通过不同方式的遍

历来生成不同形式的表达式。

首先是结点结构。与前面学过的线形链表一样，二叉树的结点也分为数据域与指针域，只不过这里

有两个指针域分别指向左右孩子节点。有时为了操作方便还会附加一个双亲指针，这里就不需要了，下

面是节点定义：



classTNode{

public:

union{charoptr;intopnd;};

TNode*left;

TNode*right;

TNode(charop,TNode*lef,TNode*rgt)

:optr(op),left(lef),right(rgt){}

TNode(intnum)

:opnd(num),left(NULL),right(NULL){}

};



在表达式中又分运算数与操作符，所以结点的数据域必须设成联合的形式。同时为了便于生成新结

点而加了两个构造函数。因为这个表达式类只是为了介绍二叉树，所以为了简便起见规定操作数只能是

1~9 的整数。

表达式类的定义很简单，只需要存储一个指向树根的指针就够了，并且不需要做任何的初始化操作。

下面是类的定义及部分函数声明。



#include"../../线性表（链式存储）/栈/Stack.h"

#include"../../require.h"

#include<iostream>

#include<string>

classExpTree{

TNode*m_pRoot;

public:

ExpTree():m_pRoot(NULL){}

~ExpTree(){destroy(m_pRoot);}

//求值

intvalue(){returnval(m_pRoot);}

private:

//销毁树

voiddestroy(TNode*cur){

if(cur){

destroy(cur->left);

destroy(cur->right);

deletecur;

}

}

//计算

intcacul(inta,charop,intb){

switch(op){

case'+':returna+b;

case'-':returna-b;

case'*':returna*b;

case'/':returna/b;

}

}

//求值函数

intval(TNode*cur){

if(cur->left==NULL&&cur->right==NULL)

returncur->opnd;

else

returncacul(val(cur->left),cur->optr,val(cur->right));

}

};



在之前的章节讲栈与递归时书上给出过一个中缀表达式求值的具体程序，在求值过程中需要用两个

栈，并且代码并不简单。而这里你会看到，对于表达式树的求值操作却非常简单，甚至只需要两条语句。

因为这里大部分操作都是递归定义，而递归函数本身都是很简洁的，甚至比你想象的还要简单！就像树

的遍历操作(我第一次看时有些惊讶，没想到如此简单)。三种遍历分别是先序遍历、中序遍历与后序遍历，

正好对应表达式的三种形式：前缀型、中缀型与后缀型。其中为大家所熟知的是中缀形式，如 2+3*(5-

4)。前缀型表达式又叫波兰式(Polish Notation)，后缀性表达式又叫逆波兰式

(ReversePolishNotation)。它们最早于 1920 年由波兰数学家 JanLukasiewicz发明，这两种表示

方式的最大特点是不需要括号来标明优先级，它们经常用于计算机科学，特别是编译器设计方面。三种

遍历方式书上讲得很详细，不再说了，并且利用 C++的封装和重载特性，这些遍历方法能很清晰的表达:



public:

//先序遍历

voidPreOrder(void(*visit)(TNode*cur)=print){

cout<<"先序遍历(波兰式)："<<endl;

PreOrder(m_pRoot,visit);

cout<<endl;

}

//中序遍历

voidInOrder(void(*visit)(TNode*cur)=print){

cout<<"中序遍历(中缀形式)："<<endl;

InOrder(m_pRoot,visit);

cout<<endl;

}

//后序遍历

voidPostOrder(void(*visit)(TNode*cur)=print){

cout<<"后序遍历(逆波兰式)："<<endl;

PostOrder(m_pRoot,visit);

cout<<endl;

}

private:

//先序遍历

voidPreOrder(TNode*p,void(*visit)(TNode*cur)=print){

if(p!=NULL){

visit(p);

PreOrder(p->left,visit);

PreOrder(p->right,visit);

}

}

//中序遍历

voidInOrder(TNode*p,void(*visit)(TNode*cur)=print){

if(p!=NULL){

InOrder(p->left,visit);

visit(p);

InOrder(p->right,visit);

}

评论收藏

内容反馈

zhyhao_871

2013-05-12

非常不错，不仅有代码，还有解释！
yqwang2006

2013-08-06

改一下可以用，但现在的算法只能是整型运算
yewenlin

2012-09-05

很感谢分享，说明得非常到位
xxxcy

2014-03-05

很靠谱的代码，谢谢分享
wisdom0102030405

2013-04-08

最近学习了这个，看了基本上明白了，谢谢分享！

前往

页

simplebelief

粉丝: 9
资源: 35

c++实现字符串表达式求值（逆波兰式）

C++代码实现逆波兰表达式

c++ 字符串表达式求值

表达式求值(逆波兰式法)

逆波兰表达式的C++实现

表达式求值源代码（逆波兰式）

字符串表达式求值

波兰表达式求值（one stack）

逆波兰式解决表达式求值问题

C++实现逆波兰式

逆波兰表达式实现

逆波兰表达式求值

后缀表达式(逆波兰式)求值

逆波兰表达式求值.md

逆波兰表达式求值源代码

逆波兰式的实现

C++编写的逆波兰式

逆波兰式 C++版

逆波兰表达式

编译原理 逆波兰式 C++实现

表达式求值，中序变后序

字符串转加减乘除表达式

java、c++表达式求值（带括号和小数点）

转化为逆波兰表达式

C++版本 逆波兰式 解析四则运算

波兰式、逆波兰式与表达式求值

逆波兰表达式求值（后缀表达式）

逆波兰表达式求值（栈实现）1

C# 表达式求值，字符串表达式求值

表达式求值（逆波兰算法，javascript实现）

最新资源

编译原理逆波兰式 C++实现

C++版本逆波兰式解析四则运算