C++ source code to convert a formula string to a RPN.

infix2rpn.cpp

/***************************************************************
  Convert an infix formula to an RPN.
  (Unary operators are not supported)

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

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

namespace my_lib {

class Infix2Rpn {
  std::string f;                   // 中置記法(infix formula)文字列
  std::vector<std::string> str2ary(std::string);  // 文字列の配列化

public:
  Infix2Rpn(std::string f) : f(f) {}  // コンストラクタ
  std::string convert();              // 中置記法 => 後置記法 変換
};

/*
 * 中置記法 => 後置記法 変換
 *
 * @return 変換後文字列(string)
 */
std::string Infix2Rpn::convert() {
  std::stack<std::string> st;  // 作業用スタック
  std::vector<std::string> v;  // 変換後配列
  std::regex re_d("\\d+");     // 正規表現（数値）
  std::regex re_k_0("\\(");    // 正規表現（括弧・開き）
  std::regex re_k_1("\\)");    // 正規表現（括弧・閉じ）
  std::unordered_map<std::string, int> kPri = {
    {"*", 3}, {"/", 3}, {"+", 2}, {"-", 2}, {"(", 1}, {")", 1},
  };                           // 演算子・括弧優先度
  std::smatch sm;              // 正規表現（マッチ部分）
  unsigned int sz_v;           // 変換後配列サイズ
  unsigned int i;              // ループインデックス
  std::string rpn;             // 変換後文字列

  try {
    for (std::string t : str2ary(f)) {
      if (std::regex_search(t, sm, re_d)) {
        v.push_back(t);
      } else if (std::regex_search(t, sm, re_k_0)) {
        st.push(t);
      } else if (std::regex_search(t, sm, re_k_1)) {
        while (st.top() != "(") {
          v.push_back(st.top());
          st.pop();
        }
        st.pop();
      } else {
        while (!st.empty() && (kPri[st.top()] >= kPri[t])) {
          v.push_back(st.top());
          st.pop();
        }
        st.push(t);
      }
    }
    while (!st.empty()) {
      v.push_back(st.top());
      st.pop();
    }
    // 配列 => 文字列（スペース区切り）
    sz_v = v.size();
    for (i = 0; i < sz_v - 1; i++) rpn += v[i] + " ";
    rpn += v[sz_v - 1];
  } catch (...) {
    return "";  // 変換失敗
  }

  return rpn;
}

/**
 * @brief      中置記法文字列の配列化
 *
 * @param[ref] 中置記法文字列 f (string)
 * @return     配列(vector)
 */
std::vector<std::string> Infix2Rpn::str2ary(std::string f) {
  std::vector<std::string> v;
  std::regex re("([0-9\\.]+|[()*/+\\-])");
  std::smatch sm;

  try {
    f.erase(remove(f.begin(), f.end(),' '), f.end());
    while (std::regex_search(f, sm, re)) {
      v.push_back(sm[1].str());
      f = sm.suffix();
    }
  } catch (...) {
    return {};  // 配列化失敗
  }

  return v;  // 配列化成功
}

}  // namespace my_lib

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

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

  return EXIT_SUCCESS;
}