区間を分割するアルゴリズム

Question

区間を分割するアルゴリズム

区間を分割して数え上げをするときの実装について質問があります。

AtCoderABC033_C
こちらの問題です。

次のような制約を満たす数式

Sが与えられます。
演算子は + (加算) と * (乗算) のみからなる。乗算を優先して計算する。括弧は存在しない。それぞれの項は、 1桁の整数である。
例えば、1+340 、 1+2+3+4+5 などの数式はこの条件を満たしますが、12+3+5、467-3、(3+4)*5+2 のような数式は 条件を満たさないため、入力として与えられません。
あなたは、この数式のうち数字の部分をいくつか選んで 0 に書き換えることで、この式の値を 0にしたいです。式の値を 0にするために 0 に書き換えなければならない数字の個数の最小値を求めてください。

問題の実装方針としては +の数の数え上げと+で囲まれた区間内に0が存在すればそれを数えて次の区間へ移動するということです。

私の実装

こちらの実装で問題は解けます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int p_cnt = 1, zero_cnt = 0;

    for(int i=0; i<s.size(); i++) {
        if(s[i] == '+') p_cnt++; // +の数を数え上げ
        
        // 区間内に0があればwhile文でインクリメントして次の区間に移動
        if(s[i] == '0') {
            zero_cnt++;
            while(s[i+1] != '+' && i+1 < s.size()) {
                i++;
            }
        }
    }
    cout << p_cnt - zero_cnt << endl;
}

質問

区間を区切って、次の区間に移動する際のwhileの実装は他にどのようなものが考えられるでしょうか？
私の実装だとwhile(s[i+1] != '+' && i+1 < s.size())でプラスの前までindexを増やし、for文の判定でもう一度インクリメントするというのは、少々わかりにくいコードになってしまっているような気がします。
こっちのコードの方が良い。または、他にも実装がありましたら教えていただきたいです。

Answer 1

'+' で切り分けるのは std::getline でできます。
'0' を含むかどうかは string::find で分かります。

#include <iostream> // cin, cout, endl
#include <sstream>  // istringstream, getline
using namespace std;

int main()
{
	string s, t;
	cin >> s;
	istringstream iss(s);
	int k = 0;
	while (getline(iss, t, '+'))
		if (t.find('0') == string::npos) k++;
	cout << k << endl;
}

追記
string::getline と書いていましたが、
getline は string のメンバ関数ではないので、std:: に修正しました。
<string> を include していませんが、<sstream> が string を使うので
その中で include されているものと思われます。

Comments

[episteme]

こっちの方が綺麗ですね、高評価。

Answer 2

'+' を区切り文字として切り分けたいなら、コレがヒントになるかしら。

#include <stdio.h>
#include <string.h>

void split(const char* str) {
  char* s = strdup(str);
  char* token;
  for ( token = strtok(s, "+"); token; token = strtok(NULL, "+") ) {
    printf("[%s] ", token);
  }
  printf("\n");
  free(s);
}
int main() {
  split("1+3*4*0");
  split("1+2+3+4+5");
  split("1*2+3*4+5*6*7");
  return 0;
}

実行結果:

[1] [3*4*0]
[1] [2] [3] [4] [5]
[1*2] [3*4] [5*6*7]