構文解析
人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…
アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…
至ってシンプルな構文解析問題。ただちょっと仕様が不明瞭なところがある気もする。 問題へのリンク 問題概要 次のように、何個かの計算式を表す文字列 が与えられるので計算結果を出力せよ。 2 4-2*3= 4*(8+4+3)= 式は数値、演算記号、かっこからなり、= で…
アドホックにも実装できそうだけど、構文解析ライブラリで殴った! 問題へのリンク 問題概要 0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ の文字列 が与えられる。たとえば以下のような文字列が与えられる。 1+2*3+4 また、Bob がこの式…
この問題のおかげで、構文解析力が上がった! 問題へのリンク 問題概要 次のように、 の関数を表す式 が与えられる。基本的には「+」「*」「^」「log」で構成されるものである。 N*log(N^2)*log(N)+N+log(N^1+N)^2*N より正確には、次の BNF によって定義さ…
BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…
こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…
構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…
せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…
構文解析、超絶苦手系だけど苦手とばかり言っていられない。 問題へのリンク 問題概要 (a)*a+((a+(a*(a))-(a)*a+a*a))*a のような文字列 が与えられる。各 a に入るデフォルトの数値 が与えられている。今 個のクエリが来て、各クエリは : 個目の a を で置…
超苦手系だと思いながら恐る恐る実装したら、ノーデバッグでサンプル全部通った上に、そのまま提出したら AC もらえて超ビックリした!!! パースして木構造作って木 DP 的なことをするのが主流かもだけど、なんかもっとアドホックにできた。 問題へのリン…