C++代码实现逆波兰式

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

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