使用C++代码实现逆波兰式的方法

本文主要介绍"使用C++代码实现逆波兰式的方法"，希望能够解决您遇到有关问题，下面我们一起来看这篇 "使用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*(&#63;2-(5+1))")() == "3 2 5 1 + - * "); // Failed Case: Can not recognize '&#63;'
return 0;
}

关于 "使用C++代码实现逆波兰式的方法" 就介绍到这。希望大家多多支持编程宝库。

本文主要介绍"C++中for循环与while循环的区别有哪些"，希望能够解决您遇到有关问题，下面我们一起来看这篇 "C++中for循环与while循环的区别有哪些" 文章。C++中for循环和 ...