公式的後序遍歷

Question

在數據結構中，我按順序進行轉換並將公式轉換預先排序爲樹。但是，我對後期訂單不太滿意。

對於給定的公式x y z + a b - c */-

我想出了

    - 
       / \ 
       * /(divide) 
      /\ /\ 
       x + - c 
       /\ /\ 
       y z a b 

在大多數情況下，這似乎符合，除了在左子樹的*屬於百搭甲板。在後序遍歷中，最後一個字符是樹的頂部節點，其他所有分支都向下。現在我將/和*運算符表示它們應該位於相對的節點上。但是，遍歷樹時，除*之外的所有東西都適合，因爲左邊的子樹必須先處理根節點之前的節點，然後切換到右邊的子樹。

讚賞正確的方向輕推。

Answer 1

圍棋秩序。首先，再次寫出整個堆棧：

X Y Z + A B - C */-

現在開始，左，尋找第一個運營商。在堆棧中替換它與先前的兩個操作數，在那裏，有一個小的階位：

X（Y + Z）AB - C */-

繼續下一個操作：

X（Y + Z）（A - b）C */-

然後下：

X（Y + Z）（（A - b）* C）/ -

x（（y + z）/（（a-b）* c）） -

X - （（Y + Z）/（（A - B）* C））

現在，使它一棵樹，​​只是在中間開始（你已經知道，因爲它是最後一個元素在原始堆棧中），並且從外部到內部掛起括號內的子表達式。

Answer 2

實際上，編寫一個解析後序表達式的程序比按順序解析它的程序更容易，因爲您不必檢查操作的優先級。

試試這個：創建一個堆棧，並在它們中添加操作數（從左到右）。當你找到一個操作時，從堆棧中提取它期望的操作數的數量並放回一棵小樹。完成後，堆棧中只有一個結果：最終的圖形。

例：

x y z + -> x + 
      /\ 
       y z