競技プログラミング風 C++問題集【第2回】

引数で与えられた文字列中の ‘1’～’3′ 文字を ‘A’～’C’ に置換した文字列を返す関数 string replace123ToABC(const string& str) を実装しなさい。

例えば、”31415926535″ が引数として渡された場合は、”ca4a59b65c5″ を返す。
[java] #include <iostream> // 標準入出力ライブラリ
#include <string>
using namespace std; // std 名前空間使用
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
string replace123ToABC(const string& str) {
// ToDo: ここに’1’～’3’を’a’～’c’に変換するコードを記述
return "";
}
int main() {
DO_TEST( replace123ToABC("") == "" );
DO_TEST( replace123ToABC("31415926535") == "ca4a59b65c5" );
DO_TEST( replace123ToABC("a01234z") == "a0abc4z" );
cout << "\nGood Job!\n";
return 0;
}
[/java]

逆ポーランド記法の式を文字列で受け取り、それを評価し、評価結果を２番めの引数に設定する関数 bool calc(const string& str, int& val) を実装しなさい。

逆ポーランド記法とは「30 2 +」の様に、演算対象を先に記述し、その後に演算子を後置する記法だ。 日本語で「30と2を足す」と読めば理解が容易だ。

逆ポーランド記法文字列にエラーがある場合・0で割った場合は false を返す。 エラーが無い場合は true を返し、評価結果を 第2引数のvalに返すものとする。

なお、数値は数字列による整数のみ、演算子は「+ – * /」のみをサポートし、演算は整数として行われるものとする（オーバーフローは無視）。

例えば、”30 2 +” が与えられた場合は true を返し、val には32が格納される。
“3 20 + 2 *” が与えられた場合は true を返し、3と20を足して、それに2を乗じると46なので、val には46が格納される。

“3 2 + *”, “2 + 3”, “3 0 /”, “a 1 +” 等が与えられた場合は false を返す。
[java] #include <iostream>
#include <string>
#include <vector>
using namespace std;
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
bool calc(const string& str, int& val) {
// 逆ポーランド記法で書かれた式 str を評価し、評価結果を val に設定し、true を返す
// 逆ポーランド記法が間違っている場合、評価時エラーが出た場合は false を返す
vector<int> stack;
for (int i = 0; i != str.size();++i) {
if (str[i] == ‘ ‘) { // 半角空白の場合はスキップ
} else if (isdigit(str[i])) { // 数字の場合
int v; // 数値文字列を変換した値
// ToDo: 数値文字列を数値に変換しスタックに積む
} else {
// ToDo: 加減乗除演算子でない場合はエラー
// ToDo: スタックに値が2つ以上無い場合はエラー
// ToDo: 演算子を判定し、スタックトップ・次で演算
}
}
if (stack.size() != 1) return false;
val = stack.back();
return true;
}
int main() {
int val;
DO_TEST(calc("123", val) && val == 123 );
DO_TEST(calc("2 3 +", val) && val == 5);
DO_TEST(calc("2 3 -", val) && val == -1);
DO_TEST(calc("20 3 + 2 *", val) && val == 46);
DO_TEST(!calc("2 + 3", val));
DO_TEST(!calc("2 a +", val));
DO_TEST(!calc("2 0 /", val));
cout << "\nGood Job!\n";
return 0;
}
[/java]