アルゴリズム問題
0, 1, &, |, ^からなるboolean expression(論理式)と、その式から導きたい答えが与えられたときに、その答えを導くような論理式への括弧のつけ方が何通りあるか答えよ。
例えば、
Expression: 1^0|0|1
Desired result: false(0)
Output: 2 ways: 1^((0|0)|1)または1^(0|(0|1))
Cracking the coding interview, 問題9.11
ひっかかった
&&は演算子式であり、&はメソッドである
演算子式...if elseなどの構文と同じグループということ
確かにそう言われると、andで代替できることもしっくりくる!
メソッド...あるクラスに対して定義されている、つまりオブジェクトに対して使われる
確かに[ruby doc](http://ruby-doc.org/core-2.3.1/)で&&の定義がなくて&があったのはそういうことだったのか!(上記リンクにはClassとMethodの定義しかない)
つまり?
Rubyリファレンスマニュアル
&&
左辺を評価し、結果が偽であった場合はその値(つまり nil か false) を返します。左辺の評価結果が真であった場合には 右辺を評価しその結果を返します。
||
左辺を評価し、結果が真であった場合にはその値を返します。 左辺の評価結果が偽であった場合には右辺を評価し その評価結果を返します。
つまり:演算子なので、if operator then 式 end
と同じ!つまり、&&、||の左右は演算子として扱われ、
(op1 && op2)の場合:「op1が真ならば、op2を返せ」
(op1 || op2)の場合:「op1が真だったらop1を返せ」
という意味になる。
ひっかかったコードおさらい
0&&1 -> 1
1&&0 -> 0
0||1 -> 0
1||0 -> 1
左辺について、両方とも、rubyでは0や1はオブジェクトとして評価されるので、真!
よって&&では、右辺の値が返り、
||では、左辺の値がそのまま返っていた!
&、| 単独だとビット演算をするメソッドなので、(00や11ではなく)0、1で計算すると論理式の結果と同じになります。
解答
上記問題の解答in ruby
何か疑問・良い解答などあれば教えていただきたいです^^
def check(exp, desired_result)
if exp.length == 1
if exp.to_i == desired_result
return 1
else
return 0
end
end
counter = 0
0.step(exp.length - 3, 2) do |start_index|
new_exp = exp.dup
calculated = cal(new_exp, start_index)
new_exp[start_index..start_index+2] = calculated.to_s
counter += check(new_exp, desired_result)
end
return counter
end
def cal(exp, start_index)
case exp[start_index+1]
when '|'
return exp[start_index].to_i | exp[start_index+2].to_i
when '&'
return exp[start_index].to_i & exp[start_index+2].to_i
when '^'
return exp[start_index].to_i ^ exp[start_index+2].to_i
end
end
print "counter = ", check('1^0|0|1', 0), "\n"