競技プログラミングにおける構文解析問題まとめ

構文解析

• 文法に基づいて文字列を認識する必要がある問題で構文解析が要求される
• ガチの構文解析は必要ないので、再帰で書けるようにしておこう
• ICPCで頻出
• 参考：参考1 問題紹介とその解説 参考2 参考3

問題

• ferinさんまとめ

• AC 異世界数式 解説
• AOJ 知識の証明 解説
• AOJ Factorization 解説
• yukicoder No.708 （＋ー）の式 解説
• AC Tournament Chart 解説
• FHC2019予選 Mr. X 解説
• CF465 Fafa and Ancient Mathematics 解説
• SRM731 Div1 Easy TreesAndBrackets 解説
• AC 数式とクエリ
• LC1028 Recover a Tree From Preorder Traversal 解説
• LC1096 Brace Expansion II
• HUPC2019C 短絡評価 解説

• 逆ポーランド記法
  • HR Jerry's Expression

以下、メモ書き

http://d.hatena.ne.jp/anta1/20121215/1355552223
https://gist.github.com/draftcode/1357281
http://ferin-tech.hatenablog.com/entry/2017/11/30/125854
https://gist.github.com/draftcode/1357281
http://noy.hatenablog.jp/entry/2017/05/22/121607
http://hamayanhamayan.hatenablog.jp/entry/2017/11/21/014003
http://hamayanhamayan.hatenablog.jp/entry/2017/03/29/120134
https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_b

• 簡単な再帰で掛けるもの
  • CF465 Fafa and Ancient Mathematics 解説
• 括弧列
  • SRM731 Div1 Easy TreesAndBrackets