今日はセメスターの始まりということもあり、人の集まりが微妙でした(延べ5+1人)。
その代わりといってはなんですが、サークルに見学に来てくれた子が居ました(！)。しかも医学科(！！！)。
勧誘はもうちょいしたら本格的にやる予定ですが、どのくらい来るんでしょうかね？
さて、今日は見学に来てくれた子の環境構築をしながらだったので、もくもく会(各自で問題を解く)という形になりました。
個人的に気になったトピックは、「構文解析」。
ICPCなんかでも割と出題されますね。基本的には数式なんかの解釈です。
とはいっても、ここで扱うのは木構造などを使わないで解ける、易しめの構文解析問題。
では早速いきましょう。
逆ポーランド記法の解釈です。問題名になっている通り、スタックを使うとうまく解けます。
スタックとは？
スタック(Stack)は、データ構造のひとつで、いわゆるLIFO(後入れ先出し)です。ちょうど、”米びつ”みたいなものをイメージしてもらうといいんじゃないでしょうか。あとから補充したお米が、かき混ぜたりしなければ最初に使われます。一番最初に入れたお米は、米びつの中が空っぽになるまで使われないということですね。
C++の標準ライブラリでは、#include<stack>した上でstd::stack<型名> オブジェクト名; と書くと宣言できます。
末尾に値を追加するメソッドはpush(値)、末尾の値を参照、削除するメソッドはそれぞれtop()、pop()です。値を取り出す操作は、topとpopの両方を行うことでできます。
逆ポーランド記法は、演算子の直前2つの数字どうしで演算を行います。例えば、” 1 2 + ” なら 3、 “3 1 – ” なら 2 という具合にです。こうすることで、 ” 1 2 + 3 * ” 、”3 1 2 + * “といった具合に、1つの演算結果を別の演算に使う際に、括弧が要らなくなるというものです(一般的な記法で表せば、それぞれ “(1 + 2) * 3″、 “3 * (1 + 2)” )。
さて、ここで注目したいのは、「直前2つの数字で演算を行う」ということです。ということは、数字をスタックに積んでおき、毎回の演算のたびにスタックから値を2つ取り出し、その結果を積む、ということを繰り返すことで目的の計算が可能になります(こちらも参考になります→http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087 )。
それと、もうひとつこの手の問題で気を遣いたいのが文字列と数字の変換です。演算子が入っている以上、入力はstring型やchar型配列など、文字列の形式で受け取るべきです。ということは、数字も文字列として扱われてしまうということです。なにも考えずにキャストしてしまうと、とんでもない答えが返ってきてしまいます。
#include <iostream>
using namespace std;
int main(){
int a = 5, b = (int)'5';
cout << a << " " << b << "\n";
return 0;
}
/*
---output---
5 53
------------
*/
5と’5’は別物です。各文字や数字には、コンピュータで扱えるようにするために番号が割り当てられています。(int)’5’では、’5’に割り当てられた番号(ASCIIコード)を参照することになるのです。char型(の配列)で扱われている数字は、atoi(文字列)という関数を用いることで変換できます。
#include <iostream>
using namespace std;
int main(){
// atoi()は引数にchar型配列(つまり文字列)を要求するので "" で囲みます
int a = 5, b = atoi("5");
cout << a << " " << b << "\n";
return 0;
}
/*
---output---
5 5
------------
*/
charのみなら、 ‘5’ – ‘0’といった具合に、’0’で引いても正しい結果になります。これは、各数字に割り当てられている番号(ASCIIコード)が連続しているからです(参考: http://www12.plala.or.jp/mz80k2/electronics/ascii/ascii.html)。
解答例です。
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
// 標準入出力の高速化
cin.tie(0);
ios::sync_with_stdio(false);
// ----------
string str;
stack<int> s;
while(cin >> str){
int a, b;
// 演算子ごとに2個取り出して計算(順番に注意)
if(str[0] == '+'){
a = s.top(); s.pop();
b = s.top(); s.pop();
s.push(b+a);
}else if(str[0] == '-'){
a = s.top(); s.pop();
b = s.top(); s.pop();
s.push(b-a);
}else if(str[0] == '*'){
a = s.top(); s.pop();
b = s.top(); s.pop();
s.push(b*a);
// 数字はスタックに積む
}else{
// c_str() : string-> *charへの変換
s.push(atoi(str.c_str()));
}
}
// 最後に残ったものが答え
cout << s.top() << "\n";
return 0;
}
もうひとつ、こちらは文字列の扱いがポイントになります。
これを構文解析といっていいのかは微妙なところですが……まあ数式を受け取ってほげほげする問題なので広義の構文解析と言ってもいいでしょう。
+と＊が混ざった数式の中で、いくつの数字を書き換えれば結果が0になるか、という問題です。ここでも、文字列の扱いがポイントになります。数式自体はスペースなどで分割こそされていませんが、制約を見ると、与えられる数字がせいぜい1桁であることに気づくでしょう。先頭から1文字ずつ見ていけば大丈夫です。
＊で繋がった部分には、1つでも0があればその結果は0になります。＋でつながっている数式はそれらすべてが0になる必要があります。まとめれば、数式を＋がくるまで見ていき、それまでに0がなければanswer++するのを繰り返せばいいことになります。数式なのにその中身を計算する必要はまったくないのです。これで下手に計算なんかしてしまうと、制約が\(S\leq10^5\) ということもあり、\(9^{50000}\) なんてレベルの計算をしてしまいかねません(実際私はそれでオーバーフローを起こしていて、WAが取れずハマっていました)。
解答例です。
#include <iostream>
using namespace std;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
char s;
int ans = 0;
bool iszero = false;
while(cin >> s){
if(s == '+'){
if(!iszero) ans++;
iszero = false;
}else if(s == '0'){
iszero = true;
}
}
if(!iszero) ans++;
cout << ans << "\n";
return 0;
}
考察、大事。アルゴリズムや標準ライブラリの便利な機能を勉強すると、ついついそれで無理やりやるような実装になりがちですが、こんな感じの簡単な実装を心がけたいですね。最近STLのlower_boundやmultisetなんかで問題を殴るようになったサークル長はそう反省したのでした。
おまけ：そういえばICPCの過去問でも、似たような構文解析の問題がありました。ICPC2015prelimB – ICPC Calculator 上に挙げたものより少し難しいですが、ぜひ挑戦してみましょう！
Pingback: 10/26定例勉強会「第一回バーチャルコンテスト」 – 東北大学puzzleknot 公式サイト