数据结构之用栈实现逆波兰表达式-创新互联
逆波兰表达式也称为后缀表达式,它将一个算数表达式不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行,如下图所示:
成都创新互联于2013年成立,先为吉安等服务建站,吉安等地企业,进行企业商务咨询服务。为吉安企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。在这里我们可以运用栈的特点来实现后缀表达式,思路如下:
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; }
运行结果如下:
写在结尾:
本次编程需要注意理解逆波兰表达式的意义,在保存元素时候注意选择用数组而不是字符串。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页名称:数据结构之用栈实现逆波兰表达式-创新互联
URL分享:http://pwwzsj.com/article/hgsep.html