逆波兰表达式的实现
一般情况下表达式是由操作数和运算符组成,例如算数表达式中通常将运算符放在两个操作数中间,譬如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://scyanting.com/article/joispp.html