Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
C++ source code to convert a formula string to a RPN.
/***************************************************************
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.