逆波兰表达式的实现
一般情况下表达式是由操作数和运算符组成，例如算数表达式中通常将运算符放在两个操作数中间，譬如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
//若函数参数一定不能为空的条件下必须用断言
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://6mz.cn/article/joispp.html