Developer

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

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

目次

‘1’~’3’を’a’~’c’に置換(難易度:★★☆☆☆)

問題

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

例えば、”31415926535″ が引数として渡された場合は、”ca4a59b65c5″ を返す。

#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;
}
ヒント

・文字列の各文字を順にチェックし、’1′, ‘2’, ‘3’ の場合は、各々を ‘a’, ‘b’, ‘c’ に置換すればいいぞ。
・各文字を順にチェックするには、for文で i を回して str[i] で各文字を参照するといいぞ。
・拡張for文を使うこともできるぞ。そうすると、コードが少しかっこよくなるぞ。

解答例
string replace123ToABC(const string& str) {
    string out = str;   //  文字列を作業用文字列にコピー
    for (auto& ch : out)    //  拡張for文ですべての文字を参照
        if (ch >= '1' && ch <= '3')     //  '1', '2', '3' の場合
            ch = ch - '1' + 'a';        //  各々を 'a', 'b', 'c' に置換
    return out;     //  置換済み文字列を返す
}
解説

文字列の各文字を順にチェックし、’1′, ‘2’, ‘3’ の場合は、各々を ‘a’, ‘b’, ‘c’ に置換すればよい。 そのためには for 文で i を回して str[i] で各文字を参照するとよいのだが、回答例のように拡張for文を使用した方が簡潔に記述できる。

逆ポーランド記法(難易度:★★★☆☆)

問題

逆ポーランド記法の式を文字列で受け取り、それを評価し、評価結果を2番めの引数に設定する関数 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 を返す。

#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;
}
ヒント

・逆ポーランド記法で書かれた式を評価するには、まず字句解析を行い、次にそれを評価するんだぞ。
・字句解析では、数字列を数値に変換し、演算子かどうかをチェックするんだぞ。
・逆ポーランド記法を評価する場合、数値はスタックに積み、演算子はスタック上の2つの値を演算するんだぞ。

解答例
bool calc(const string& str, int& val) {
    vector<int> stack;
    for (int i = 0; i != str.size(); ++i) {
        if (str[i] == ' ') {        //  空白文字はスキップ
        } else if (isdigit(str[i])) {      //  数字文字の場合
            int v = str[i] - '0';       //  数字文字→数値変換
            while(isdigit(str[i+1]))    //  数字文字が続く場合
                v = v * 10 + str[++i] - '0';    //  現在の値を10倍し、文字の数値を加える
            stack.push_back(v);         //  数値をスタックにプッシュ
        } else {
            if (str[i] != '+' && str[i] != '-' && str[i] != '*' && str[i] != '/')
                return false;   //  不正な演算子の場合はエラー
            if (stack.size() < 2) return false;     //  スタックに値が2つ無い場合はエラー
            auto top = stack.back();    //  スタックトップ取り出し
            stack.pop_back();       //  スタックトップ消去
            switch (str[i]) {
            case '+':   stack.back() = stack.back() + top; break;   //  加算処理
            case '-':   stack.back() = stack.back() - top; break;   //  減算処理
            case '*':   stack.back() = stack.back() * top; break;   //  乗算処理
            case '/':   
                if (top == 0) return false;     //  0除算エラー
                stack.back() = stack.back() / top; break;   //  除算処理
            }
        }
    }
    if (stack.size() != 1) return false;    //  スタックに値がひとつだけでない場合はエラー
    val = stack.back();     //  スタックトップを取り出す
    return true;
}
解説

逆ポーランド記法で書かれた式を評価するには、まず字句解析を行い、次にそれを評価する。 字句解析と言っても、本問題では字句の種類は数値と四則演算子だけなので、 回答例のようにfor分で文字を順に見ていき、半角空白・数字文字・演算子文字で処理を分けるだけだ。
半角空白はスキップするだけだ。
数字文字の場合は、数字文字が続くあいた、それを数値に変換していく。最初は ‘0’ を引いて v に格納し、 2文字目以降はvを10倍し、str[++i] – ‘0’ を加える。この手順で10進数文字列を数値に変換できる。
数字文字以外が現れたら数値が確定するので、その数値をスタックにプッシュする。
半角空白・数字文字でない場合は else 部分に行き、四則演算子かどうかをチェックし、そうでなければエラーとする。
演算子の場合は、スタックトップと次を演算するので、スタックに値が2つ無い場合はエラーとする。 あとは、トップの値と次を取り出し演算して結果をまたスタックトップに積む。

以上を最後まで処理したら、スタックに値が一つだけあるかをチェックし、OKならば、スタックトップの値を評価結果として返す。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。