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;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。