数据结构之用栈实现逆波兰表达式
逆波兰表达式也称为后缀表达式,它将一个算数表达式不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行,如下图所示:
成都创新互联是专业的衡阳县网站建设公司,衡阳县接单;提供网站制作、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行衡阳县网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
在这里我们可以运用栈的特点来实现后缀表达式,思路如下:
1.首先当遇到运算操作数时将其进行push操作;
2.当遇到操作符是将此时的栈pop两次,先取出的栈顶为右操作数;
3.执行此方法到整个数组遍历完。
我们在这里采用了数组来存储后缀表达式中的元素,因为如果用字符串保存的话,首先解析字符串的时候会比较麻烦(既有数字还有字符),其次数组的大小控制也比较方便。
利用枚举的方法将所要用到的运算符和操作数罗列出来
enum Type { OPERAND, //操作数 OPERATOR, //操作符 ADD,//加法 SUB,//减法 MUL,//乘法 DIV//除法 };
这样方便我们后面的操作,可以在自由增减我们需要的运算方法。
#include#include #include using namespace std; enum Type { OPERAND, //操作数 OPERATOR, //操作符 ADD,//加法 SUB,//减法 MUL,//乘法 DIV//除法 }; struct Cell { Type _type; int _value; }; int CountRPN(Cell _a[], size_t _size) { stack s; for (size_t i = 0; i < _size; i++) { //如果是操作数进行push操作 if (_a[i]._type == OPERAND) { s.push(_a[i]._value); } //如果是操作符则先将当前栈顶元素取出 //再取出另一个操作数做运算 //注意:先取出的数为右操作数(在减法和除法中要区分开来) if (_a[i]._type == OPERATOR) { 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 RPNArray[] = { { OPERAND, 12 }, { OPERAND, 3 }, { OPERAND, 4 }, { OPERATOR, ADD }, { OPERATOR, MUL }, { OPERAND, 6 }, { OPERATOR, SUB }, { OPERAND, 8 }, { OPERAND, 2 }, { OPERATOR, DIV }, { OPERATOR, ADD } }; int ret = CountRPN(RPNArray, sizeof(RPNArray) / sizeof(RPNArray[0])); cout << ret << endl; system("pause"); return 0; }
运行结果如下:
写在结尾:
本次编程需要注意理解逆波兰表达式的意义,在保存元素时候注意选择用数组而不是字符串。
分享名称:数据结构之用栈实现逆波兰表达式
本文地址:http://myzitong.com/article/pdship.html