けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

構文解析

AtCoder ABC 338 G - evall (橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

AOJ 1282 Bug Hunt (ICPC アジア 2007 H) (450 点)

アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…

AOJ 0109 スマート計算機 (PCK)

至ってシンプルな構文解析問題。ただちょっと仕様が不明瞭なところがある気もする。 問題へのリンク 問題概要 次のように、何個かの計算式を表す文字列 が与えられるので計算結果を出力せよ。 2 4-2*3= 4*(8+4+3)= 式は数値、演算記号、かっこからなり、= で…

AOJ 1346 Miscalculation (ICPC アジア 2014 B) (200 点)

アドホックにも実装できそうだけど、構文解析ライブラリで殴った! 問題へのリンク 問題概要 0 以上 9 以下の整数値に対して「+」「×」で連結して得られる長さ の文字列 が与えられる。たとえば以下のような文字列が与えられる。 1+2*3+4 また、Bob がこの式…

TTPC 2023 F - N^a (log N)^b

この問題のおかげで、構文解析力が上がった! 問題へのリンク 問題概要 次のように、 の関数を表す式 が与えられる。基本的には「+」「*」「^」「log」で構成されるものである。 N*log(N^2)*log(N)+N+log(N^1+N)^2*N より正確には、次の BNF によって定義さ…

AOJ 2584 壊れた暗号生成器 (ICPC 模擬国内 2014 C) (400 点)

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>…

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C) (250 点)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 2613 Unordered Operators (JAG 夏合宿 2013 day3-G) (350 点)

構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…

AOJ 2401 恒等式 (JAG 模擬国内 2012 C)

せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…

2018 codeFlyer 本選 E - 数式とクエリ (700 点)

構文解析、超絶苦手系だけど苦手とばかり言っていられない。 問題へのリンク 問題概要 (a)*a+((a+(a*(a))-(a)*a+a*a))*a のような文字列 が与えられる。各 a に入るデフォルトの数値 が与えられている。今 個のクエリが来て、各クエリは : 個目の a を で置…

AOJ 1188 階層民主主義 (ICPC 国内予選 2013 C) (350 点)

超苦手系だと思いながら恐る恐る実装したら、ノーデバッグでサンプル全部通った上に、そのまま提出したら AC もらえて超ビックリした!!! パースして木構造作って木 DP 的なことをするのが主流かもだけど、なんかもっとアドホックにできた。 問題へのリン…