Re: [問題]唯一樹造的出來嗎?

[LPH66 ((short)(-15074))]

※ 引述《joeyeh (joe)》之銘言：
: inorder:  (3*(5-1/3*3)/(23 x^y 3)+2.5 e^x) x^0.5
: preorder: x^0.5 +/*3-5/1*3 3 x^y 23 3 e^x2.5
: 開方根運算符號我用x^0.5來代表,鍵盤上找半天找不到
: 學長真狠.....怎麼造...
以下用  ^ 表示 x^y
       √ 表示 開根號
      exp 表示 自然指數

前序為:

√ + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5

前提: √ 和 exp 是單元函數  其他是二元函數

首先先括號 (為什麼能先括號等會講)

√ + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5
√ + / * 3 - 5 / 1 (* 3 3) ^ 23 3 exp 2.5
√ + / * 3 - 5 (/ 1 (* 3 3)) ^ 23 3 exp 2.5
√ + / * 3 (- 5 (/ 1 (* 3 3))) ^ 23 3 exp 2.5
√ + / (* 3 (- 5 (/ 1 (* 3 3)))) ^ 23 3 exp 2.5
√ + / (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3) exp 2.5
√ + (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) exp 2.5
√ + (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) (exp 2.5)
√ (+ (/ (* 3 (- 5 (/ 1 (* 3 3)))) (^ 23 3)) (exp 2.5))

所以對應的中序是 √(((3*(5-(1/(3*3))))/(23^3))+(exp 2.5))

如果像上面的表示法  單元函數把函數放後面的話

(此處用 sqrt 表根號...因為頗不直覺)

就是 (((3*(5-(1/(3*3))))/(23^3))+(2.5 exp)) sqrt
---
我覺得你問錯問題了....

運算式只需要其中之一就可以推得其他兩個

因為運算式裡面只有 operand 才是葉節點  同樣的只有 operator 才是非葉節點

所以可以輕易從這裡推得其他兩個 (這也是剛剛括號的依據)

一般的樹的表示法則不一定誰才是葉  所以才需要兩個
---
那麼就來看看一般的樹的版本  (沿用 sqrt 為根號)

前序 sqrt + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5
中序 3 * 5 - 1 / 3 * 3 / 23 ^ 3 + 2.5 exp sqrt

一個重點: 前序第一個東西必然是根

所以 sqrt 是根  對照中序可知它只有左邊有東西

                                        sqrt
                         ┌───────┘
前序 + / * 3 - 5 / 1 * 3 3 ^ 23 3 exp 2.5
中序 3 * 5 - 1 / 3 * 3 / 23 ^ 3 + 2.5 exp

+ 是根。

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
前 / * 3 - 5 / 1 * 3 3 ^ 23 3     exp 2.5
中 3 * 5 - 1 / 3 * 3 / 23 ^ 3     2.5 exp

右邊比較簡單: exp 是根  2.5 在左邊

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
前 / * 3 - 5 / 1 * 3 3 ^ 23 3     exp
中 3 * 5 - 1 / 3 * 3 / 23 ^ 3    ┌┘
                                2.5

左邊: / 是根....但不知道哪一個才是根?

簡單: 前序和中序的元素個數是一樣的

所以如果中序的第一個 / 是根  那同樣取前面 5+1 個元素會得到不合理的東西

因此中序的第二個 / 是根

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
       ┌───┴────┐      ┌┘
前 * 3 - 5 / 1 * 3 3   ^ 23 3   2.5
中 3 * 5 - 1 / 3 * 3   23 ^ 3

同樣右邊簡單:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
       ┌───┴────┐      ┌┘
前 * 3 - 5 / 1 * 3 3     ^      2.5
中 3 * 5 - 1 / 3 * 3   ┌┴┐
                       23   3

左邊: 看似中序的第一個 * 是根...第二個如何? 似乎也很合理...

先試第二個好了:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
         ┌──┴────┐      ┌┘
         *               ^      2.5
     ┌─┴────┐  ┌┴┐
前 3 - 5 / 1 * 3   3   23   3
中 3 * 5 - 1 / 3

同樣  兩個 3 誰才是根呢? 第一個試試看:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
         ┌──┴────┐      ┌┘
         *               ^      2.5
     ┌─┴────┐  ┌┴┐
     3             3   23   3
     └──┐
      前 - 5 / 1 * 3
      中 * 5 - 1 / 3

- 是根...怪了  怎麼式子不合理? (左子樹前 5 / 中 * 5 )

所以這裡不對  那換試第二個 3 是根呢:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
           ┌─┴────┐      ┌┘
           *             ^      2.5
       ┌─┴───┐  ┌┴┐
       3           3   23   3
     ┌┘
前 - 5 / 1 * 3
中 3 * 5 - 1 /

依然 - 是根...又不合理了 (左子樹前 5 / 1 中 3 * 5)

所以這表示那個 * 並不是第二個 * 才是根

第一個 * 才是

捲回去吧:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
       ┌───┴────┐      ┌┘
       *                 ^      2.5
 ┌──┴──┐        ┌┴┐
 3 前 - 5 / 1 * 3 3    23   3
   中 5 - 1 / 3 * 3

這次 - 還是根  不過子樹的字串就合理了:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
       ┌───┴────┐      ┌┘
       *                 ^      2.5
 ┌──┴──┐        ┌┴┐
 3           -         23   3
   ┌────┴─┐
   5   前 / 1 * 3 3
       中 1 / 3 * 3

下面不用我說你也可以做得出來:

                                        sqrt
                         ┌───────┘
                         +
               ┌────┴────┐
               /                  exp
       ┌───┴────┐      ┌┘
       *                 ^      2.5
 ┌──┴──┐        ┌┴┐
 3           -         23   3
       ┌──┴─┐
       5         /
             ┌─┴─┐
             1       *
                   ┌┴┐
                   3   3

正好這個例子能解出唯一樹來...

我猜你學長想說的是  當節點的名字重覆時也許會出現不一樣的樹

最簡單的例子是:

    X   X
  ┌┘ └┐   這兩個樹前序和中序和後序都是 XX 誰知道你哪個是哪個...
  X       X

因此用前中/中後建出原來的樹有個條件是節點的名字需要各不同

而運算式方面則因為已經有剛剛說的那個條件在了

所以除了可以唯一決定外  更只需要其一即可
---
給 end 了的其他 puzzle 版眾:

http://0rz.tw/8w8sn

這篇文章在說的是這個東西
---
資料結構啊...那已經是好幾年前學的東西了...(遠目)

--
  'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
  'That makes me sound a lot cooler then I was,' Ron mumbled.
  'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
                               -- Harry Potter and the Deathly Hollows, P.308

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.28.92
推 puzzlez:我沒有END呀...雖然還是看不懂..噗....我先看連結好了....
推 puzzlez:嗯，有點像在分析英文文法..但對象是數學式的感覺...
→ puzzlez:理解到這裡就可以了..@@"
推 th11211:哈哈~這真得是資料結構,最近剛考完XD
推 joeyeh:感謝解答
推 joeyeh:開平方根為單運算元符,在中序您習慣將運算元歸左子樹?
→ joeyeh:老師是說中序括號不省是2D壓成1D所會造成的混謠
→ LPH66:應該說我在概念上會習慣將單元運算子放在運算元左邊
→ LPH66:實際實作上就不一定了
→ LPH66:至於中序加括號的問題的確如此  也因此才有優先序出現
→ joeyeh:Unary operator沒有左子樹
→ joeyeh:所以我認為您中序中把sqrt放在最後...你知道的
推 puzzlez:聽說原PO在當兵XDDDDDDD