逆波兰表达式的实现

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

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

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

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

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

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

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

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<stack>

#include<assert.h>

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 <int> s;

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

assert(a);

for(size_t i=0;i<size;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<<CountRNP(a, size)<<endl;

system("pause");

return 0;

}

运行结果：