解説
まずを処理するところから始めます。
「カーソル」を使って、以下のように実装するのが良いでしょう:
- まずカーソルをの最初の文字に置き、また演算子をいれる配列を作ります。
- カーソルの指す文字が
Aの場合、ANDを配列に追加し、カーソルを3つ進めます。 - カーソルの指す文字が
Oの場合、ORを配列に追加し、カーソルを2つ進めます。 - カーソルの指す文字が
Xの場合、XORを配列に追加し、カーソルを3つ進めます。
では計算しましょう。これは3回に分けて行うのが良いでしょう。
ANDのみを処理した数列(スタック)と、AND以外の演算子を入れる配列を作ることを考えます。
- まずにを入れます。
- その後、が
ANDの場合、の最後の要素とをして、の最後の要素を計算結果で置き換えます。 - が
ORまたはXORの場合、をに追加し、演算子をに追加します。
これでANDの処理が完了したので、同様にORを処理したあとの数列を作り(演算子配列は処理後に全てXORになるので不要です)、その要素を全てXORで計算すれば最終的な結果が得られます。
計算量はです。
Bonus:配列を一回だけ走査する形で実装してみましょう。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。