42 SILICON VALLEY Piscine 2017の個人プロジェクト、3つ目はevalexpr。文字列として入力された四則演算を計算し、結果を出力するものだ。個人プロジェクトとして最後の課題となるためか、Day02～13までの学習内容を包含した出題内容となっている。関連するのは、例えば次の課題だ。
| Day03 | ft_atoi |
| Day05 | atoi ft_str_is_alpha ft_str_is_numeric |
| Day07 | ft_split_whitespace |
| Day08 | ft_split_whitespace |
| Day11 | スタック、pushとpop |
| Day13 | 木構造 |
evalexprを実装するに際し、これらすべてを使用する必要はないのだがatoiの使用は避けられないだろう。スタックと木構造の使用は受講者次第だ。私は使用していないのだが、人によっては数式を木構造、スタックへ変換し、あるべき順序での計算するために使用するだろう。
例によって問題は詳細を語らず、一部の解釈を受講者に委ねている節がある。
この投稿では、次の話題を採り上げている。
- 問題の分析と仕様策定：対応すること、しないことの判断
- 考え方、アプローチ
- 実装
これまで同様、サンプル・コードはPythonで記述した。Piscine受講生に配慮して、C言語的な記述になるよう配慮している。1月実施のPiscineまで1週間に迫ろうとしている。この投稿がPiscine受講生の一助になれば、と思う。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
evalexpr
Create a program called eval_expr.
• It’ll have a function eval_expr prototyped as follows :
int eval_expr(char *str);
• This function takes a characters string as argument. This string represents an arithmetic expression. For example :
"3 + 42 * (1 - 2 / (3 + 4) - 1 % 21) + 1"
• This expression must be calculated and its result must be returned.
• The following five operators must be supported :
◦ + for addition
◦ - for subtraction
◦ / for division
◦ * for multiplication
◦ % for modulo
• The function must also support any amount of brackets.
文字列として入力された数式を計算し、答えを出力することを求められている。
プログラム以前に、この問題には注意すべき事柄が含まれている。まず課題を分析してみる。
分析と仕様
提供される数式は、適切なものが提供されるのだという。従って、数式中に余計な文字が含まれていないか、「()」の組み合わせが適切であるか、などと言ったことをプログラムで考慮する必要はない。
• The string passed as argument will be valid (nobugs, nobogusaddresses, no letters or syntax errors, no division by zero, etc...).
数式には半角スペースが含まれている。演算子と数字の間にはスペースが含まれるかもしれないが、「)」と数字の間にスペースは含まれていない。
計算処理の前に、何らかの方法で半角スペースを取り除くのが良いだろう。この処理はDay07、08の学習が活きるだろう。まず数式全体を、区切り文字が半角スペースの文字列として処理すればよい。
もちろん、半角スペースを無視しながら、一文字ずつ確認してもよい。私は後者を採用する。
数式に含まれる数字はどうだろうか？例えば「3 / 2」が入力された場合、暗算や電卓上での答えは「1.5」だが、プログラム上ではデータ型に依存する。int型の場合は「1」だ。前者に対応するにはdouble、float型の数値処理に対応する必要がある。
Piscineでは教えられていない関数の仕様はチートと見なされ、減点対象となる。そして課題を一通り確認する限り、それらは教えられていない。数式に含まれる数値から、その回答まで、全ての数値をint型として処理することにした。小数点が数式に含まれることはない前提で、その対応処理も実装しない。
符号はどうだろうか？符号には演算子として処理するものに加え、「-」を負の数の接頭辞として処理しなければならない場合もある。負の数をどのように処理するだろうか。私には一案がある。負の数を正の数を含む数式に変換するのだ。例えば、このような具合だ。
「-4」→(0 - 4)
四則演算の順序を守るため、単純に「0 -」とするだけでなく、「()」で囲むことを忘れない。こうすることで、例外的な処理を共通化することができる。
数式には「()」が含まれる。()内の処理は最優先で処理しなければならないが、これも「-」の処理同様、例外的であり可能ならば共通化したいところだ。私は提供された数式全体を「()」で囲むことにした。このような具合だ。
「10 * (2 + 3)」→(10 * (2 + 3))
こうすることで、やはり例外的な処理を共通化することができる。
ここまでをまとめると、プログラムの仕様はこのようになる。
| 適切な数式が入力される。 | 数式の検証処理をしない。 |
| 半角スペースを無視する。 | |
| 全ての数値をintとして処理する。 | 小数点の処理をしない。 |
| 負の数を「0 -」で数式化する。 | |
| 数式全体を「()」で囲む。 |
考え方とアプローチ
まず四則演算のおさらいから。
- 「()」の式を先に計算する。
- 掛け算、割り算、剰余算を、足し算、引き算よりも先に計算する。
数式には「()」が含まれる。()内には式が含まれる。つまり式の入れ子構造だ。「()」を見つけて優先的に処理するので、プログラムは再帰処理を伴う。以前、再帰の説明で次のことに触れた。
- 最初に呼ばれた関数が、最後に結果を返す。
- 最後に呼ばれた関数が、最初に結果を返す。
今回は各処理を関数化することにする。この前提で考えると、処理は次の順序になるはずだ。
| 処理の順番 | 結果を返す順番 | 処理 | 関数 | |
| 1 | 4 | 足し算、引き算 | 式の処理 | expression |
| 2 | 3 | 掛け算、割り算、剰余算 | 項の処理 | term |
| 3 | 2 | 「()」内の処理 | 因子の処理 | factor |
| 4 | 1 | 文字列の数値化 | atoi charからintへ変換 |
number |
数式中の足し算、引き算を計算するためには、必要な()内の式、掛け算、割り算、剰余算の結果を待たなければならない。最終的に、数式は足し算、引き算にまとまる。つまり足し算、引き算の処理とは「式」の処理だ。
式に含まれる数値は掛け算、割り算、剰余算の結果だ。それは式を構成する「項」となる。()内に含まれる式は、一つずつ数値、演算子を評価していく。それらは項を構成する「因子」となる。特に数値については、文字列から数値へ変換して対応しなければならない。
ちなみに、これは「再帰下降法」、「再帰下降構文解析」と呼ばれる処理だ。
www.google.com
ここで一つだけ、Piscine受講生は真似できない、Pythonならではの仕組みを用いることにする。私は数式の処理中に、必要な都度、数値変換を紛れ込ませたくない。数式処理に先立って、入力された数式の数字を、あらかじめ数値に変換しておきたい。
そこでreformatという関数を作成し、事前に数式を「()」、演算子、数値に分けたlist（配列）に格納した上で、数式処理は純粋に、構文解析に集中させようと思う。
先に紹介したnumberに相当する処理は、このサンプルではreformat中に実施することになる。
実装
reformat
引数valとして入力された数式を一文字ずつ判別していく。半角スペースは無視する。「-」を見つけたら、「分析と仕様」で触れた数式化の処理を行う。数字をint型へ変換するためにatoiを用いた。ここではmy_atoiとして実装している。
数式には「()」、演算子、数字しか含まれない前提なので、is_numberで判定した結果によって、数値として処理するか、それ以外として処理するかを分岐している。
出来上がったlistは、引数aryに格納される。
グローバル変数として定義している「p」は、Cで言うところの文字列ポインタに相当する。現在の参照位置を表している。実装はこのようになる。
def reformat(val, ary): global p minus_flg = 0 while True: if val[p] == '\n': ary.append(val[p]) break if val[p] == ' ': p += 1 if val[p] == '-': if is_number(val[p + 1]) == True: minus_flg = 1 ary.append('(') ary.append(0) ary.append('-') p += 1 continue if is_number(val[p]) == False: ary.append(val[p]) p += 1 continue else: ary.append(my_atoi(val[p:])) if minus_flg == 1: ary.append(')') minus_flg = 0
expression
足し算、引き算を処理する。まず左辺を取り出し、演算子が「+、-」のいずれかであれば、右項を取得するために、項の処理であるtermへ移行する。注意したいのは引き算の、コード記述の順序だ。
数式「A - B」が与えられたとして、最初に左辺Aを取り出している。termの戻り値が右辺Bだが、この時「term() - A」としてはならない。足し算、掛け算では記述順序の影響はないが、それ以外では計算結果に影響するので注意する。
グローバル変数として定義している「i」は、reformatで生成した配列のインデックスだ。現在の参照位置を表している。実装はこのようになる。
全ての結果を得たら、計算結果を返す。実装はこのようになる。
def expression(ary): global i print('expr', '\t', ary[i:]) ret = term(ary) while ary[i] != '\n': if ary[i] == '+': i += 1 ret = ret + term(ary) elif ary[i] == '-': i += 1 ret = ret - term(ary) else: break; return ret
term
計算が掛け算などに変わっただけで、処理内容の構造はexpressionと変わりない。そのため実装例は割愛する。必要ならば、末尾のサンプル・コードを参照してほしい。
割り算、剰余算の記述順序に注意すること。
factor
因子の処理を司るのだが、一つ重要なのが「()」の存在だ。「(」を見つけたら、優先的に処理すべき式が始まる。ここが再帰の入り口だ。改めてexpressionを呼び出す必要がある。
そうでなければ、数値を取得することになる。本来作成すべき関数numberは、ここで呼び出すことになる。
グローバル変数として定義している「i」は、expressionで紹介したものと同一の変数だ。Pythonでは関数ごとにグローバル変数を定義しなければならない。C言語ならばポインタで済むところなのだが。
実装はこのようになる。
def factor(ary): global i print('factor', '\t', ary[i:]) if ary[i] == '(': i += 1 ret = expression(ary) i += 1 else: ret = ary[i] i += 1 return ret
本来不要なのだがデバッグ用の出力として、サンプル・コードの各関数の先頭に、その関数が参照している数式を表示させている。各関数が想定通りの順番で呼び出しされていること、同時に、それらが参照している数式に注目してほしい。
同じくデバッグ用の出力として、プログラム実行後に、与えられた数式をコンソールで計算した結果も出力している。プログラムの結果と、本来の実行結果を照合している。
例えば、数式「(1+2+3) * (-1) * 10 + 100」を与えると、次の出力結果が得られる。数式の先頭から順番に処理していると同時に、四則演算の計算順序に則した結果を得ていることが理解できるはずだ。
expr ['(', '(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term ['(', '(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor ['(', '(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
expr ['(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term ['(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor ['(', 1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
expr [1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term [1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [1, '+', 2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term [2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [2, '+', 3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term [3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [3, ')', '*', '(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor ['(', '(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
expr ['(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term ['(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor ['(', 0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
expr [0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term [0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [0, '-', 1, ')', ')', '*', 10, '+', 100, ')', '\n']
term [1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [1, ')', ')', '*', 10, '+', 100, ')', '\n']
factor [10, '+', 100, ')', '\n']
term [100, ')', '\n']
factor [100, ')', '\n']
from eval 40
from console 40
余談
一通りの文章に目を通していただいて、ありがとう。
1月実施のPiscineまで1週間に迫ろうとしている。C言語は先に他の言語を習得しても、馴染みにくいプログラム言語で、特に初学者は苦労させられているかもしれない。
もしC言語以外に馴染みのある言語があるのであれば、まずその言語で課題に挑戦し、それをC言語で書き直してみてはどうだろうか。少なくとも実装すべきロジックが明らかなのであれば、馴染みの言語とC言語との差分を意識しさえすれば良いのだから、負担は軽減されるはずだ。
何よりPiscineは入学試験である、ということを忘れてはいけないだろう。全てのプログラムを解いて満点を取れるようには作られておらず、何かしら受験生間に差の出る仕組みが取り入れられているはずだ。プログラムがどのように評価されるのかは分からないが、all or nothingではなく、何らかの部分点が得られるような仕組みがあるのではないだろうか。
やれるところまでやってみる、最低限でも動作する仕組みまでは実装できることを優先するならば、一度、他の言語で試してみて、それをC言語で書き直すことをしてみるのは、対策として有効な試みになるかもしれない。
実際のところ、42 SV Piscine 2017のプロジェクト課題は考えさせられる、悩まされるレベルの難易度のものが含まれているのだが、各日の課題については、それほど難しいものではない。
以前、私はPiscine学習のためには推薦しないと述べたのだが、それら課題の難易度は、下記書籍に掲載されている練習問題と同程度だ。決して難問、奇問の類ではないし、時間をかければ解けるものばかりだ。
手を抜かぬよう、そして挫折しないように。
By Odin, by Thor ! Use your brain !!!
サンプル・コード
