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