C++代码实现逆波兰式

时间:2022-04-15 09:04:09

100行以内C++代码实现逆波兰式

逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。

算术表达式转逆波兰式例子:

C++代码实现逆波兰式

逆波兰式整体的算法流程图如下:

C++代码实现逆波兰式

下面给出我基于C++ 语言对逆波兰式算法的实现代码,值得注意的是:

1、算法中对操作数,仅支持一个字符的字母或数字的操作数,如:x,y,j,k,3,7等;如果要支持多个字符的操作数,如:var1,3.14等。需要读者自己扩展对算术表达式操作数的分词部分的代码。

2、为了为了增加转换后的逆波兰表达式的可读性,我在每个操作数和操作符输出时后面追加了一个空格。

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/// 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);
};
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/// 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;
}

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

原文链接:https://blog.csdn.net/weixin_46222091/article/details/104858135