大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

逆波兰表达式的实现

  一般情况下表达式是由操作数和运算符组成,例如算数表达式中通常将运算符放在两个操作数中间,譬如a+b的形式,这种形式称为中缀表达式,那么问题来了,是否有后缀表达,前缀表达式呢???

创新互联网站建设公司,提供网站制作、成都网站设计,网页设计,建网站,PHP网站建设等专业做网站服务;可快速的进行网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,是专业的做网站团队,希望更多企业前来合作!

   

对,没错,这些后缀表达,前缀表达式都是由波兰数学家Jan Lukasiewicz提出来的

把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;

把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+;

逆波兰表达式的实现

    假如我们有一个表达式,应该如何求它的值呢?在这里栈就派上用场了,由于操作数在操作符前边,所以按顺序遍历这个表达式,遇到操作数的时候就进栈,遇到操作符的时候就让离操作符最近的两个操作数出栈,并参加运算,然后将运算结果压入栈中。过程如下图所示:

逆波兰表达式的实现

要编写逆波兰表达式求解函数,就要将一个逆波兰式当做一个数组去处理,而且这个数组应该是一个结构体数组,每个数组元素包含两个内容,一个是数组元素的类型(操作数类型还是操作符类型),一个是这个类型对应的值。

 今天就暂且实现一下后缀表达式吧,在这里运用枚举,能够更清晰的表达哦

#define _CRT_SECURE_NO_WARNINGS 1

#include

#include

#include

using namespace std;

enum Type

{

OP_NUM,

OP_SYMBOL,

};

enum SYMBOL

{

ADD,

SUB,

MUL,

DIV,

};

//定义一个结构体数组包括数组的类型和数组的值

struct Cell

{

Type _type;

int _value;

};

//逆波兰表达式计算函数

int CountRNP(Cell a[],size_t size)

{

stack s;

//若函数参数一定不能为空的条件下必须用断言

assert(a);

for(size_t i=0;i

{//数组里边的元素若为数值,则直接压入栈中

if(a[i]._type==OP_NUM)

{

s.push(a[i]._value);

}

//若数组里边的元素不是值,而是运算符,则将离运算符最近的两个元素出栈,进行运算

else

{

int right=s.top();

s.pop();

int left=s.top();

s.pop();

switch(a[i]._value)

{

case ADD:

s.push(left+right);

break;

case SUB:

s.push(left-right);

break;

case MUL:

s.push(left*right);

break;

case DIV:

s.push(left/right);

break;

default:

break;

}

}

}

return s.top();

}

int main()

{

Cell a[]={{OP_NUM, 12},{OP_NUM, 3},{OP_NUM, 4},

         {OP_SYMBOL,ADD},{OP_SYMBOL,MUL},

 {OP_NUM, 6},{OP_SYMBOL,SUB},{OP_NUM, 8},{OP_NUM, 2},

         {OP_SYMBOL,DIV},{OP_SYMBOL,ADD}};

size_t size =sizeof(a)/sizeof(Cell);

cout<

system("pause");

return 0;

}


运行结果:

逆波兰表达式的实现


文章标题:逆波兰表达式的实现
本文链接:http://dzwzjz.com/article/joispp.html
在线咨询
服务热线
服务热线:028-86922220
TOP