概述
栈有什么用呢?我们可以用栈解决很多难以解决的问题。例如:括号匹配问题、逆波兰表达式(也叫后缀表达式)、迷宫等问题,这些问题我们都可以用栈来解决。
今天我们就来看看用栈如何解决逆波兰表达式问题。
什么是逆波兰表达式呢?我们表述一个算式通常是这样:X + Y,即:“操作数1 操作符 操作数2”,当然也有比较特别的,比如“sqrt(N)”,sqrt是操作符,N是操作数,而逆波兰表达式则很统一,先操作数后操作符,为什么叫“逆波兰表达式”?因为有一个波兰人发明了波兰表达式,而逆的波兰表达式就叫“逆波兰表达式”了。我们来看一下下边的图就很容易理解了:
或许看图还是不是很清楚这个是怎么计算的。
那我就再来解释一下:
其实很简单,我们只要把这个表达式给出来,然后获取它的每一项,判断这一项是数据还是操作符,如果是数据,则我们让它入栈,如果是操作符,我们让数据出栈,和操作符进行运算,在这里我们要特别注意,当遇到操作符时,操作符不入栈,取此时栈顶元素,为操作符的右操作数,出栈,再取此时栈顶元素为操作符的左操作数,这里的左操作数和右操作数顺序不能颠倒,不然运算结果有时会出现错误,最后,再让出栈的2个元素运算的结果入栈,再继续向后进行。
我解释一下为什么操作符左右操作数颠倒可能会出错:
到这里我估计大家也明白了这个逆波兰表达式的求解方式了吧,那我们就来看看代码吧。
RPN.h //头文件
#ifndef __RPN_H__
#define __RPN_H__
#include<stdio.h>
#include<assert.h>
#define MaxSize 20
typedef int SDataType;
typedef struct Stack
{
int top;
SDataType arry[MaxSize];
}Stack;
typedef enum
{
Add = 0,
Sub,
Mul,
Div,
Data
}OPERATOR;
typedef struct Cell
{
OPERATOR _op;
int data;
}Cell;
int CalcRPN(Cell* RPN, int size);
void StackPush(Stack* ps, SDataType data);
void StackPop(Stack* ps);
void StackInit(Stack* ps);
#endif //__RPN_H__
RPN.c //源文件
#include"RPN.h"
void StackInit(Stack* ps)
{
assert(ps != NULL);
ps->top = 0;
}
void StackPush(Stack* ps, SDataType data)
{
assert(ps != NULL);
ps->arry[ps->top] = data;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps != NULL);
ps->top--;
}
int CalcRPN(Cell* RPN, int size)
{
Stack s;
StackInit(&s);
int right = 0;
int left = 0;
int i = 0;
int ret = 0;
assert(RPN != NULL);
while (i < size)
{
//是数据,入栈
if (Data == RPN[i]._op)
{
StackPush(&s, RPN[i].data);
i++;
}
else //是运算符,进行运算
{
StackPop(&s);
right = (&s)->arry[(&s)->top];
StackPop(&s);
left = (&s)->arry[(&s)->top];
switch (RPN[i]._op)
{
case Add:
ret = left + right;
StackPush(&s, ret);
i++;
break;
case Sub:
ret = left - right;
StackPush(&s, ret);
i++;
break;
case Mul:
ret = left * right;
StackPush(&s, ret);
i++;
break;
case Div:
ret = left / right;
StackPush(&s, ret);
i++;
break;
}
}
}
return (&s)->arry[--(&s)->top];//返回当前栈顶元素,就是最后的元素结果,[--(&s)->top]为什么要--呢,是因为出栈的时候top先--,再取元素,top指向的是栈顶元素的上边,这个我在前边的博客中有解释
}
入栈的有数据和四则运算的操作符,那我们可以把它定义成一个枚举类型,里边有DATA,ADD,SUB,MUL,DIV这些操作,我们为这个函数定义一个结构体,结构体里边有操作类型和数据。
我们在给测试表达式的时候可以以数组的形式给出,数组中每一个元素的类型都是结构体类型,有操作类型和数据,如果操作类型是操作符,我们就把它的数据给为0,当然也可以是其他数,因为我们用不到它。
test.c //测试文件
#include"RPN.h"
void test()
{
Cell RPN[] = { { Data, 12 }, { Data, 3 }, { Data, 4 }, { Add, 0 }, { Mul, 0 }, { Data, 6 }, { Sub, 0 }, { Data, 8 }, { Data, 2 }, { Div, 0 }, { Add, 0 } };
int size = sizeof(RPN) / sizeof(RPN[0]);
int ret = CalcRPN(RPN, size); //size是数组大小
printf("%dn", ret);
}
int main()
{
test();
return 0;
}
最后
以上就是潇洒诺言为你收集整理的逆波兰表达式(后缀表达式)的全部内容,希望文章能够帮你解决逆波兰表达式(后缀表达式)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复