2026-11-11
calc.cpp
#include <string_view>
int evaluate(std::string_view s) {
}
数字と + - * / と括弧だけからなる式の文字列 s を計算して返す evaluate を書いてください。* と / は + と - より先に計算し、同じ強さの演算子どうしは左から順に計算します。数は0以上の整数で何桁でもよく、空白は含みません。/ は int の割り算と同じく0の方向へ切り捨てます。s は正しい式で、0で割ることはなく、途中の値も int に収まるものとします。
入力例 1
evaluate("100-20/3-4")
出力例 1
90
入力例 2
evaluate("2*(3-5)*(8/(1+1))")
出力例 2
-16
入力例 3
evaluate("7")
出力例 3
7
Reference
Reference
#include <string_view>
namespace {
int expr(std::string_view& s);
bool next_is(std::string_view s, char c) {
return !s.empty() && s.front() == c;
}
int factor(std::string_view& s) {
if (next_is(s, '(')) {
s.remove_prefix(1);
int v = expr(s);
s.remove_prefix(1);
return v;
}
int v = 0;
while (!s.empty() && s.front() >= '0' && s.front() <= '9') {
v = v * 10 + (s.front() - '0');
s.remove_prefix(1);
}
return v;
}
int term(std::string_view& s) {
int v = factor(s);
while (next_is(s, '*') || next_is(s, '/')) {
char op = s.front();
s.remove_prefix(1);
int rhs = factor(s);
v = op == '*' ? v * rhs : v / rhs;
}
return v;
}
int expr(std::string_view& s) {
int v = term(s);
while (next_is(s, '+') || next_is(s, '-')) {
char op = s.front();
s.remove_prefix(1);
int rhs = term(s);
v = op == '+' ? v + rhs : v - rhs;
}
return v;
}
} // namespace
int evaluate(std::string_view s) {
return expr(s);
}
優先順位の段ごとに関数を1つずつ用意しました。expr は + と - でつながった並びを、term は * と / でつながった並びを、factor は数か括弧で囲んだ式を読みます。低い段の関数は1段高い段の関数を呼んでオペランドを読むので、expr が - の右を term で読んだ時点で 20/3 は1つの値 6 にまとまり、割り算が先に済みます。括弧は factor から一番低い段の expr に戻って読むことで、中身全体を1つのオペランドとして扱えます。これは参考実装で、唯一の正解ではありません。
同じ段の演算子は、while で左から順に v へ畳み込みます。100-20/3-4 では v が 100、94、90 と変わり、左から計算した 90 が返ります。どの段の関数も同じ std::string_view を参照で受け取り、読んだ分だけ remove_prefix で先頭を進めるので、呼び出しから戻った側は続きの位置から読めます。next_is で空かどうかを先に確かめるのは、式の終わりで front() を呼ばないためです。
2*(3-5)*(8/(1+1)) では、factor が ( を見るたびに expr を呼び、内側の expr は ) を見ると自分の担当する演算子ではないのでループを抜けて戻ります。閉じ括弧は呼び出した factor が読み飛ばし、値は −2 と 4 になって、全体は 2 × (−2) × 4 = −16 です。7 のように演算子の無い式では、どのループも1回も回らず、factor が読んだ7がそのまま返ります。