「AOJ1155 How can I satisfy thee? Let me count the ways...」の編集履歴（バックアップ）一覧に戻る
*AOJ1155 How can I satisfy thee? Let me count the ways...
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp]
**問題俯瞰
問題は与えられた式をある規則によって計算した結果が2となるときのP, Q, Rの組み合わせ数を答えるものです。
P, Q, Rは0, 1, 2とそれぞれ値が変化するので３重ループのfor文で回して27通り試しそのたびに構文解析をし直せばよいです。
Sample Inputが2となりものがあり、その結果27を返すものがあります。これはP, Q, Rがそれぞれいかなる値でも常に計算結果が2であるのでP, Q, Rの組み合わせ数は27通りということを示します
**解説
以下の与えられたBNF((BNF = バッカス・ナウア記法(Backus-Naur form)といいます。２人の人の名前をつなげてます))に従って再帰的下向き構文解析のコードを書くのみです。
>||
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula> | (<formula>*<formula>) | (<formula>+<formula>)
||<
電卓のときは<expression> <term> <factor>というように3つの要素がありましたが、今度は<formula>のみなので作る再帰関数もformula()のみ存在すれば必要十分です。
参考文献 → [https://gist.github.com/draftcode/1357281:title=構文解析 Howto]
さて、先に与えられた表の計算の仕組みを考えなければなりません。
XやY(この場合それぞれ<formula>)があるときに与えられている真理表において -X, (X*Y), (X+Y) はどのような仕組みで行われているでしょうか。
パターン数が少ないので演算の関係をすべて表に埋め込んでも良いですが、ちょっと格好良く（？）やりたいところです。
-X は 0が2, 1が1, 2が0 となります。if文を3つ書いても良いですが、「2からXを引く」とすれば
順に、2から0引いて2、2から1引いて1、2から2引いて0となり優雅に一行で済ませられます。
(X*Y)や(X+Y)はどうでしょう。やはりこれもパターン数が少ないので結果を配列に格納して条件分岐を用いて解くという方法も考えられますが、じっと見て優雅に解きましょう。
XとYの数の対応を見て
>>
(X*Y) 数の大きい方の数字を選んでいる＝両者のmaxを取ればよい
(X+Y) 数の小さい方の数字を選んでいる＝両者のminを取ればよい
<<
となると思います。
BNFのうち簡単なものから処理しましょう。構文解析する上で読み進めるポインタの挙動を考えるのはひとまず後回しにします。
0 | 1 | 2 | P | Q | R | の部分はそれぞれの文字を読み込んだときに具体的な値やP, Q, Rの変数の値を返せば良さそうです。
-Xについては上に示したとおりで、併せて以下のように書けます。
>||
int formula() {
...
switch( *p ) {
case '-': return 2 - formula();
case 'P': return P;
case 'Q': return Q;
case 'R': return R;
case '0': return 0;
case '1': return 1;
case '2': return 2;
...
}
||<
これでBNFの以下の部分全てが解析出来ました。（と思えればOKです）
>||
<formula> ::= 0 | 1 | 2 | P | Q | R |
-<formula>
||<
残すは括弧がある計算式です。計算方法は説明したとおりなのでポインタの挙動を考えなければ下のように書けます。
'('を読めたら、<formula>を読んで結果を保持し、 * or + で分岐してさらに<formula>を読み取り演算します。
>||
...( 0 | 1 | 2 | P | Q | R の部分)
case '(':
int form1 = formula();
int form2;
...
switch( *p ) {
case '*':
form2 = formula();
...
return min( form1, form2 );
case '+':
form2 = formula();
...
return max( form1, form2 );
}
}
...
||<
ここまで書ければ残すはポインタの挙動を考えるのみです。
（因みにstringの要素を参照できればよいだけなので、str[pos]としてもイテレータを用いても何でも良いです。好みの問題です）
[https://gist.github.com/draftcode/1357281:title=構文解析 Howto] では、文字を調べた直後にイテレータをインクリメントしています。つまり上のコードに記述するとしたら、
>||
case 'P':
p++;
return P;
||<
というようになります。これでよいです。ただインクリメントの書き漏らしや書きすぎが怖いので私は以下のようにしましました。
>||
int formula() {
p++;
switch( *p ) {
...
case 'P': return P;
}
||<
先に位置をインクリメントしてその後にそこの位置にある文字を調べる、とするとp++を書く回数が少なくて済みます。
ただし、
前者の「文字を調べてからインクリメント」方式と
後者の「インクリメントしてから文字を調べる」方式では、解析する数式の先頭位置が異なります。
前者は p = str.c_str(); として先頭からはじめて良いですが、後者は p = str.c_str() - 1; として先頭アドレスの一つ前を指定しなければならないので注意が必要です。自分がバグを生まないと思える書き方をするとよいです
====
補足：
stringのc_str()メソッドはstring型をconst char* 型（）として出力します。const char* 型とは文字列定数を扱う型で、C言語のprintf()関数の中の " " で囲まれる部分に相当します。読み取り専用の文字列です。
====
構文解析のように再帰的手続きを記述する場合は、具体的に考えすぎず目的の動作を抽象化してまとめてみると良いです。
解析位置を動かす基準はこうである、といえればバグを埋め込みにくくなります。
あとは終わり括弧の読み飛ばしに注意してコードを書いてみましょう。以下がその例です。
>||
#include <iostream>
#include <algorithm>
using namespace std;
int P, Q, R;
const char *p;
int formula() {
p++;
switch( *p ) {
case '-': return 2 - formula();
case 'P': return P;
case 'Q': return Q;
case 'R': return R;
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '(':
int form1 = formula();
int form2;
p++;
switch( *p ) {
case '*':
form2 = formula();
p ++;
return min( form1, form2 );
case '+':
form2 = formula();
p++;
return max( form1, form2 );
}
}
return 0;
}
int main() {
string str;
while(getline(cin, str)) {
int cnt = 0;
if( str == "." ) break;
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
P = i, Q = j, R = k;
p = str.c_str()-1;
if( formula() == 2 ) cnt ++;
}
}
}
cout << cnt << endl;
}
return 0;
}
||<
