C++ で、入力した数式の文字列を逆ポーランド記法(RPN; 後置記法)に変換する処理を実装してみました。(ついでに、後置・中置・前置記法での計算も)
前回・前々回はスタックを使用した処理についてでした。

今回は二分木を使用した処理についてです。

0. 前提条件

  • Debian GNU/Linux 10.6 (64bit) での作業を想定。
  • GCC 9.2.0 (G++ 9.2.0) (C++17) でのコンパイルを想定。
  • 演算子は *, /, +, - を想定。(単項演算子は非対応)
  • 括弧は (, ) のみに対応。

1. アルゴリズム

次のリンク先(分かりやすく、きれいにまとまっている)のとおり。(自分で説明しようとすると、煩雑化しそう)

2. C++ ソースコードの作成

infix2rpn_bt.cpp
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
/***************************************************************
  Convert an infix formula to an RPN (by binary tree).
  (Unary operators are not supported)

    DATE          AUTHOR          VERSION
    2020.10.08    mk-mode.com     1.00 新規作成

  Copyright(C) 2020 mk-mode.com All Rights Reserved.
***************************************************************/
#include <iostream>   // for cout
#include <regex>      // for regex_search.
#include <string>

namespace my_lib {

/*
 * @brief  Node クラス
 */
class Node {
  std::string expr;         // このノードが表す式
  Node *n_left  = nullptr;  // 子ノード(左)
  Node *n_right = nullptr;  // 子ノード(右)
  std::string rm_most_outer_bracket(std::string);  // 数式の最も外側のカッコを除去
  int get_operator_pos(std::string);               // 演算子の位置

public:
  Node(std::string expr) : expr(expr) {}  // コンストラクタ
  bool valid_bracket();                   // 丸カッコ対応数チェック
  void parse();                           // 解析(二分木に分割)
  void gen_post();                        // 変換(後置記法(逆ポーランド記法; RPN))
  void gen_in();                          // 変換(中置記法(挿入記法))
  void gen_pre();                         // 変換(前置記法(ポーランド記法))
  double calc();                          // 値の計算
};

/*
 * @brief  丸カッコ対応数チェック
 *
 * @return OK|NG (true|false)
 */
bool Node::valid_bracket() {
  bool res  = true;       // 結果(true|false)
  unsigned int nest = 0;  // 丸カッコのネスト数
  unsigned int i;         // ループインデックス

  try {
    for (i = 0; i < expr.size(); ++i) {
      if (expr[i] == '(') ++nest;
      if (expr[i] == ')') {
        --nest;
        if (nest < 0) break;
      }
    }
    if (nest != 0) res = false;
  } catch (...) {
    return false;
  }

  return res;
}

/*
 * @brief  解析(二分木に分割)
 */
void Node::parse() {
  int pos;  // 演算子の位置

  try {
    // 数式の最も外側のカッコを除去
    expr = rm_most_outer_bracket(expr);
    //# 演算子の位置
    pos = get_operator_pos(expr);
    // 演算子が存在しない場合、項とみなす
    if (pos < 0) return;
    // 子ノード(左)
    n_left = new Node(rm_most_outer_bracket(expr.substr(0, pos)));
    n_left->parse();
    // 子ノード(右)
    n_right = new Node(rm_most_outer_bracket(
          expr.substr(pos + 1, expr.size())));
    n_right->parse();
    // 演算子
    expr = expr[pos];
  } catch (...) {
    throw;
  }

  return;
}

/* @brief     数式の最も外側のカッコを除去
 *
 * @param[in] 括弧除去前の文字列(string)
 * @return    括弧除去後の文字列(string)
 */
std::string Node::rm_most_outer_bracket(std::string s) {
  bool res  = false;             // true: 数式の最も外側にカッコあり, false: なし
  unsigned int sz_s = s.size();  // 文字列長さ
  unsigned int nest = 0;         // カッコのネスト数
  unsigned int i;                // ループインデックス
  std::smatch sm;                // 正規表現マッチ

  try {
    // 最初の文字が "(" の場合、最も外側にカッコがあると仮定
    if (s[0] == '(') {
      res  = true;
      nest = 1;
    }
    // 2文字目以降、チェック
    for (i = 1; i < sz_s; ++i) {
      if (s[i] == '(') {
        ++nest;
      } else if (s[i] == ')') {
        --nest;
        // 最後以外でカッコが全て閉じられた場合、最も外側にカッコはないと判断
        // 例:"(1+2)+(3+4)"などの場合
        if (nest == 0 && i < sz_s - 2) {
          res = false;
          break;
        }
      }
    }
    // 最も外側にカッコがない場合、元の文字列をそのまま返す
    if (!res) return s;
    // カッコ内が空の場合、エラー
    if (std::regex_match(s, sm, std::regex("^\\(\\)$"))) {
      std::cout << "[ERROR] Empty bracket! (" << s << ")" << std::endl;
    }
    // 最も外側のカッコを除去
    s = s.substr(1, s.size() - 2);
    // 更に最も外側にカッコが残っている場合、再帰的に処理
    if (std::regex_match(s, sm, std::regex("^\\(.*?\\)$"))) {
      s = rm_most_outer_bracket(s);
    }
  } catch (...) {
    throw;
  }

  return s;
}

/*
 * @brief     演算子の位置取得
 *
 * @param[in] 数式文字列(string)
 * @return    演算子の位置(int)
 */
int Node::get_operator_pos(std::string s) {
  // 演算子の位置が不正なら、終了
  if (s == "") return -1;

  int pos = -1;               // 演算子の位置初期化
  unsigned nest = 0;          // カッコのネスト数
  unsigned int pri_min = 4;   // 演算子のこれまでで最も低い優先度
                              // (値が大きいほど優先度高)
  unsigned int pri;           // 演算子の優先度
  unsigned int i;             // ループインデックス

  try {
    for (i = 0; i < s.size(); ++i) {
      pri = 0;  // 演算子の優先度
      if (s[i] == '=') {
        pri = 1;
      } else if (s[i] == '+' || s[i] == '-') {
        pri = 2;
      } else if (s[i] == '*' || s[i] == '/') {
        pri = 3;
      } else if (s[i] == '(') {
        ++nest;
        continue;
      } else if (s[i] == ')') {
        --nest;
        continue;
      } else {
        continue;
      }
      if (nest == 0 && pri <= pri_min) {
        pri_min = pri;
        pos = i;
      }
    }
  } catch (...) {
    return 0;
  }

  return pos;
}

/*
 * @brief  変換(後置記法(逆ポーランド記法; RPN))
 */
void Node::gen_post() {
  try {
    if (n_left)  n_left->gen_post();
    if (n_right) n_right->gen_post();
    std::cout << expr << " ";
  } catch (...) {
    throw;
  }

  return;
}

/*
 * @brief  変換(中置記法(挿入記法))
 */
void Node::gen_in() {
  try {
    if (n_left && n_right) std::cout << "(";
    if (n_left) n_left ->gen_in();
    std::cout << expr;
    if (n_right) n_right->gen_in();
    if (n_left && n_right) std::cout << ")";
  } catch (...) {
    throw;
  }

  return;
}

/*
 * @brief  変換(前置記法(ポーランド記法))
 */
void Node::gen_pre() {
  try {
    std::cout << expr << " ";
    if (n_left)  n_left->gen_pre();
    if (n_right) n_right->gen_pre();
  } catch (...) {
    throw;
  }

  return;
}

/*
 * @brief  値の計算
 *
 * @return 計算結果(double)
 */
double Node::calc() {
  if (!n_left || !n_right) return stod(expr);

  double op_l;       // オペランド(左)
  double op_r;       // オペランド(右)
  double res = 0.0;  // 計算結果

  try {
    op_l = n_left->calc();
    op_r = n_right->calc();
    if (expr == "+") {
      res = op_l + op_r;
    } else if (expr == "-") {
      res = op_l - op_r;
    } else if (expr == "*") {
      res = op_l * op_r;
    } else if (expr == "/") {
      res = op_l / op_r;
    }
  } catch (...) {
    return 0.0;
  }

  return res;
}

/*
 * @brief  実行クラス
 */
class Infix2RpnBt {
  std::string f;  // 中置記法(infix formula)文字列

public:
  Infix2RpnBt(std::string f) : f(f) {}  // コンストラクタ
  void exec();
};

void Infix2RpnBt::exec() {
  std::regex re("(\\s+)");  // 正規表現(1個以上のスペース)
  std::string s = "";       // 空文字(スペース除去用)

  try {
    // スペース除去
    f = std::regex_replace(f, re, s);
    // Node クラスのインスタンス化
    my_lib::Node n_root(f);
    // 丸カッコ対応数チェック
    if (!n_root.valid_bracket()) {
      std::cout << "[ERROR] Brackets are unbalanced!" << std::endl;
      return;
    }
    // 解析(二分木分割)
    std::cout << "---" << std::endl;
    std::cout << "                Formula: " << f << std::endl;
    n_root.parse();
    // 変換(後置記法(逆ポーランド記法; RPN))
    std::cout << "Reverse Polish Notation: ";
    n_root.gen_post();
    std::cout << std::endl;
    // 変換(中置記法(挿入記法))
    std::cout << "         Infix Notation: ";
    n_root.gen_in();
    std::cout << std::endl;
    // 変換(前置記法(ポーランド記法))
    std::cout << "        Polish Notation: ";
    n_root.gen_pre();
    std::cout << std::endl;
    // 値の計算
    std::cout << "                Answer = "
              << n_root.calc() << std::endl;
  } catch (...) {
    throw;
  }
}

}  // namespace my_lib

int main(int argc, char* argv[]) {
  std::string buf;

  try {
    std::cout << "Formula? ";
    getline(std::cin, buf);
    if (buf.empty()) return EXIT_SUCCESS;
    my_lib::Infix2RpnBt i2r(buf);
    i2r.exec();
  } catch (...) {
    std::cerr << "EXCEPTION!" << std::endl;
    return EXIT_FAILURE;
  }

  return EXIT_SUCCESS;
}

3. ソースコードのコンパイル

1
$ g++ -std=c++17 -Wall -O2 --pedantic-errors -o infix2rpn_bt infix2rpn_bt.cpp

4. 動作確認

実行後、数式を入力・エンターすると、各種記法と計算結果が出力される。

1
2
3
4
5
6
7
8
$ ./infix2rpn_bt
Formula? (1 + 2.3 * (13 - 9)) / ((20 + 25) - 6 * 2)
---
                Formula: (1+2.3*(13-9))/((20+25)-6*2)
Reverse Polish Notation: 1 2.3 13 9 - * + 20 25 + 6 2 * - /
         Infix Notation: ((1+(2.3*(13-9)))/((20+25)-(6*2)))
        Polish Notation: / + 1 * 2.3 - 13 9 - + 20 25 * 6 2
                Answer = 0.309091

以上。