読者です 読者をやめる 読者になる 読者になる

AOJ 0264: Finite Field Calculator

構文解析

問題

Finite Field Calculator | Aizu Online Judge

問題概要

  • 四則演算が与えられます。
  • modの世界の四則演算らしいです。(問題文に詳細な設定が書かれてる)
  • 結果を出力して下さい。

解法

  • 構文解析
  • 四則演算の構文解析を何気に初めてやった気がするのでやり方を書く。
  • <四則演算>:: = <剰余> ('+' or '-') <剰余>  ('+' or '-') <剰余> ...
  • <剰余>:: = <括弧> ('*' or '/') <括弧> ('*' or '/') <括弧> ...
  • <括弧>:: = <数字> or ('(' <四則演算> ')')
  • <数字>:: =  [0...9]+
  • 以上のBNFっぽいのをそのまま書くだけ
  • 割り算を求めるときに x^p-2 を知る必要があるのでそこは繰り返し二乗法。
ソースコード

感想

四則演算の構文解析はライブラリ化したほうがいい。

逆ポーランド(?)っぽくスタックを使うともっと華麗にかけるらしい。

 

こちらを参考にしました。

構文解析 Howto