逆波兰表达式的实现-创新互联
一般情况下表达式是由操作数和运算符组成，例如算数表达式中通常将运算符放在两个操作数中间，譬如a+b的形式，这种形式称为中缀表达式，那么问题来了，是否有后缀表达，前缀表达式呢？？？
对，没错，这些后缀表达，前缀表达式都是由波兰数学家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; } 运行结果： 创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文标题：逆波兰表达式的实现-创新互联
文章来源：http://cdiso.cn/article/depjej.html
