使えるのは+
,-
,*
,/
と0-9
の数字と()
の括弧のみ
ここでの正当性とは、適切な式のフォーマットを満たしているかどうかを調べる。四季を拡大解釈することによってとれる解釈をできるだけ取り除き最低限のコード記述で済むようにする。
規則は以下の通りとなる
- 数字は正負どちらも可とする
+
,-
,*
,/
は基本的に2回連続で来ない。2回連続で来る場合、2回目は-
のみを算術記号としてではなく負の数を表すマイナスとして解釈する。- 数字も連続で来ない。
- 計算で用いる
()
以外のかっこ{}
,[]
は()
で書き換えることができるため、用いずに置換する。 - 閉じ括弧
)
と開括弧(
の数は同数であること。 - 式の最後には算術記号は来ない。
もう少し詳しく式を見つめることでもう少し厳格な規則が現れる可能性はあるが、現時点で上記の規則で十分であるのでこれまでとする。
この規則によって与えられた文字列を評価することは難しくなく、また前もって正当性の評価を行うことで後の処理をより簡潔に記述することができるため行う。
式の正当性のチェックで引っかかった式はこれ以降の処理を行わない。
式としての正当性が担保された文字列は次に、式の要素に分解していく。式の要素とは+-*/
の算術記号、()
の括弧、そして数字の3種類のことであり、文字列を式の要素の集合へと変換する。
前準備で与えられた文字列が式の体裁をなしているかを確認した。次は式を解釈し計算ができるようにする。
式の解釈に置いて重要なのは算術記号の優先順位、カッコの取り外しである。
ここでは与えられた式(中置記法で記述されている)を後置記法に書き換えることにした。
後置記法に書き換えるメリットとしては、カッコのない後置記法はスタックを用いて計算が容易であるため実装面、今後の拡張性という点において非常に優秀である。
四則演算+-*/
のうちa † b(†は何らかの演算子)
とb † a(†は何らかの演算子)
が同じであるのは+,*
の2つ。
なので+,*
は結合性がある。
-,/
は数字を入れ替えると意味が変わってしまう。
また、-,/
はa † b † c == (a † b) † c
が成立するので左にのみ結合性が認められるため、左結合性。
一般に四則演算記号4つは計算の優先順位だけで分けられがちだが、他の観点を導入することですべての演算子が異なる性質を持っていることがわかる。
結合性 | 左結合性 | |
---|---|---|
優先順位 高 | * | / |
優先順位 低 | + | - |
累乗を表す^
はa † b † c == (a † b) † c
を満たさず、
a † b † c == a † ( b † c )
を満たす。
なのでこれは右結合性である。
操車場アルゴリズム(Shunting-yard Algorithm)が今回中置記法から後置記法に変換するときに用いているアルゴリズムである
https://qiita.com/tiyoda_xamarin_god/items/7ecabd7a06f0e9f4aadb https://ja.wikipedia.org/wiki/%E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0