逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。下面是一些例子：

正常的表达式 逆波兰表达式

a+b ---> a,b,+

a+(b-c) ---> a,b,c,-,+

a+(b-c)*d ---> a,b,c,-,d,*,+

a+d*(b-c)--->a,d,b,c,-,*,+

a=1+3 ---> a=1,3 +

通过后缀表达式计算表达式值的过程：顺序访问表达式的每一项，若该项为操作数，则将其压入栈中；若该项是操作符<op>,则连续从栈中退出两个操作数X和Y，形成运算指令X<op>Y，将其结果重新压入栈中。当表达式的每一项都访问并处理，则其计算结果就是当前栈顶存放的值。

下面我们以表达式4+3*4+3*（1+5）———>434*+315+*+

源程序：

#pragmaonce#include<iostream>#include<assert.h>#include<stack>usingnamespacestd;enumType{OP_NUM,OP_SYMBOL,};enumSYMBOL{ADD,SUB,MUL,DIV,};structCell{Type_type;int_value;};doubleCountRNP(Cell*a,size_tsize){assert(a);stack<double>s;doubleright=0;doubleleft=0;for(size_ti=0;i<size;i++){if(a[i]._type==OP_NUM){s.push(a[i]._value);}else{if(s.empty()){return0;}right=s.top();if(s.empty()){return0;}s.pop();left=s.top();s.pop();switch(a[i]._value){caseADD:s.push(left+right);break;caseSUB:s.push(left-right);break;caseMUL:s.push(left*right);break;caseDIV:if(left==0){cout<<"error"<<endl;}else{s.push(right/left);}break;}}}returns.top();}

测试代码：

#include"calculate.h"intmain(){Cella[]={{OP_NUM,4},{OP_NUM,3},{OP_NUM,4},{OP_SYMBOL,MUL},{OP_SYMBOL,ADD},{OP_NUM,3},{OP_NUM,1},{OP_NUM,5},{OP_SYMBOL,ADD},{OP_SYMBOL,MUL},{OP_SYMBOL,ADD}};size_tsize=sizeof(a)/sizeof(a[0]);cout<<CountRNP(a,size)<<endl;system("pause");return0;}

结果：