C++代碼實現(xiàn)逆波蘭式

更新時間：2020年11月01日 10:18:23 作者：ronnie88597

這篇文章主要為大家詳細介紹了C++代碼實現(xiàn)逆波蘭式，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

100行以內(nèi)C++代碼實現(xiàn)逆波蘭式

逆波蘭式（Reverse Polish notation，RPN，或逆波蘭記法），也叫后綴表達式（將運算符寫在操作數(shù)之后）。

算術表達式轉(zhuǎn)逆波蘭式例子：

逆波蘭式整體的算法流程圖如下：

下面給出我基于C++ 語言對逆波蘭式算法的實現(xiàn)代碼，值得注意的是：

1、算法中對操作數(shù)，僅支持一個字符的字母或數(shù)字的操作數(shù)，如：x，y，j，k，3，7等；如果要支持多個字符的操作數(shù)，如：var1，3.14等。需要讀者自己擴展對算術表達式操作數(shù)的分詞部分的代碼。

2、為了為了增加轉(zhuǎn)換后的逆波蘭表達式的可讀性，我在每個操作數(shù)和操作符輸出時后面追加了一個空格。

代碼如下：

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

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: