100行以内c++代码实现逆波兰式
逆波兰式(reverse polish notation,rpn,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。
算术表达式转逆波兰式例子:
逆波兰式整体的算法流程图如下:
下面给出我基于c++ 语言对逆波兰式算法的实现代码,值得注意的是:
1、算法中对操作数,仅支持一个字符的字母或数字的操作数,如:x,y,j,k,3,7等;如果要支持多个字符的操作数,如:var1,3.14等。需要读者自己扩展对算术表达式操作数的分词部分的代码。
2、为了为了增加转换后的逆波兰表达式的可读性,我在每个操作数和操作符输出时后面追加了一个空格。
代码如下:
/// file: reversepolishnotation.h #include <string> #include <stack> class reversepolishnotation { private: std::string _expr; unsigned _idx; std::stack<std::string> _stk; public: reversepolishnotation(const std::string &expr); std::string nextword(); std::string operator()(); static int getoppriority(const std::string &word); bool isword(const std::string &word); bool isoperator(const std::string &word); };
/// file: reversepolishnotation.cpp #include <iostream> #include <cassert> #include "reversepolishnotation.h" #include <cctype> #include <sstream> using std::cout; using std::endl; reversepolishnotation::reversepolishnotation( const std::string &expr) : _idx(0), _expr(expr) {} std::string reversepolishnotation::nextword() { if (_idx >= _expr.length()) { return ""; } return _expr.substr(_idx++, 1); } std::string reversepolishnotation::operator()() { std::stringstream outexpr; std::string word; std::string topelem; while (true) { word = nextword(); if (isword(word)) { outexpr << word << " "; } else if (isoperator(word)) { if (_stk.empty() || _stk.top() == "(") { _stk.push(word); continue; } topelem = _stk.top(); while (getoppriority(topelem) > getoppriority(word)) { outexpr << topelem << " "; _stk.pop(); if (_stk.empty()) { break; } topelem = _stk.top(); } _stk.push(word); } else if (word == "(") { _stk.push(word); } else if (word == ")") { while (true) { topelem = _stk.top(); _stk.pop(); if (topelem == "(") { break; } assert(!_stk.empty() && "[e]expr error. missing '('."); outexpr << topelem << " "; } } else if (word == "") { while (!_stk.empty()) { topelem = _stk.top(); assert (topelem != "(" && "[e]expr error. redundant '('."); outexpr << topelem << " "; _stk.pop(); } break; } else { assert(false && "[w]>>>can not recognize this word"); } } return outexpr.str(); } int reversepolishnotation::getoppriority(const std::string &word) { if (word == "+") { return 1; } if (word == "-") { return 1; } if (word == "*") { return 2; } if (word == "/") { return 2; } return 0; } bool reversepolishnotation::isword(const std::string &word) { return isalpha(word.c_str()[0]) || isdigit(word.c_str()[0]); } bool reversepolishnotation::isoperator(const std::string &word) { return word == "+" || word == "-" || word == "*" || word == "/"; } /// ---测试代码--- int main() { assert(reversepolishnotation("a+b*c")() == "a b c * + "); assert(reversepolishnotation("(a+b)*c-(a+b)/e")() == "a b + c * a b + e / - "); assert(reversepolishnotation("3*(2-(5+1))")() == "3 2 5 1 + - * "); // assert(reversepolishnotation("3*((2-(5+1))")() == "3 2 5 1 + - * "); // failed case: redundant '(' // assert(reversepolishnotation("3*(?2-(5+1))")() == "3 2 5 1 + - * "); // failed case: can not recognize '?' return 0; }
以上就是c/c++开发分享C++代码实现逆波兰式的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596970.html