羅德興老師的教學歷程檔案 - 中華科技大學數位化學習歷程

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式形式，在逆波蘭記法中，所有運算子置於運算元的後面，因此也被稱為字尾表示法、後序表示法。逆波蘭記法不需要括號來標識運算子的優先級。

在開始撰寫程式前，要先來介紹一下前序(Prefix Notation)、中序(Infix Notation)和後序(Postfix Notation)的算式，它們差別是在運算子(operator，如+、-、*、/)和運算元(operand，如12、-3)的放置順序。我們腦袋習慣使用的是中序算式，例如「1加2」，寫作1 + 2。若是要用前序算式來表示「1加2」，要寫成+ 1 2；若是要用後序算式來表示「1加2」，要寫成1 2 +。

之所以會在中序之外又多了前序和後序，是為了方便電腦程式進行運算，因為前序和後序不像中序這樣有運算子優先權以及括號內的算式要先算的問題。前序只要從右邊算到左邊，而後序更只要單純從左邊算到右邊就好了。

前序式又稱Polish Notation(PN)；中序式又稱Normal Polish Notation(NPN)；後序式又稱Reverse Polish Notation(RPN)。

前序式、中序式、後序式的運算方式

前序式的運算

首先要從右往左邊找到連續的兩個運算元和一個運算子，將它們做運算。- + 2 * 3 1 9，會先看到* 3 1，將其作「三乘一」的運算(注意這邊不是「一乘三」)後放回原本的前序式取代掉* 3 1，所以此時待計算的前序式會變成- + 2 3 9。

接著以同樣的方式，再從右往左看，找到連續的兩個運算元和一個運算子，將它們做運算。- + 2 3 9，會先看到+ 2 3，將其作「二加三」的運算(注意這邊不是「三加二」)後放回原本的前序式取代掉+ 2 3，所以此時待計算的前序式會變成- 5 9。

然後還是以同樣的方式，再從右往左看，找到連續的兩個運算元和一個運算子，將它們做運算。由於只剩下- 5 9，將其作「五減九」的運算(注意這邊不是「九減五」)後就是答案(-4)了。

中序式的運算

對於中序式，我們要從左邊往右邊看，從括號內往括號外看，且先乘除後加減。

其實大家如果有念過小學的話應該都知道要怎麼算中序式，這邊就不再雞婆多做介紹了。以下是2 * (3 + 1) - 5 * 3的計算過程：

後序式的運算

首先要從左邊往右邊找到連續的兩個運算元和一個運算子，將它們做運算。2 3 1 * + 9 -，會先看到3 1 *，將其作「三乘一」的運算後放回原本的後序式取代掉3 1 *，所以此時待計算的後序式會變成2 3 + 9 -。

接著以同樣的方式，再從左往右看，找到連續的兩個運算元和一個運算子，將它們做運算。2 3 + 9 -，會先看到2 3 +，將其作「二加三」的運算後放回原本的後序式取代掉2 3 +，所以此時待計算的前序式會變成5 9 -。

然後還是以同樣的方式，再從左往右看，找到連續的兩個運算元和一個運算子，將它們做運算。由於只剩下5 9 -，將其作「五減九」的運算後就是答案(-4)了。

前序式、中序式、後序式的轉換

中序式轉後序式

按照四則運算順序，將中序式的所有運算子和其兩側的運算元用括號括起來。例如a + b * c - d / e，會變成( ( a + ( b * c ) ) - ( d / e ) )。

接著從最外層括號開始，將右括號取代為括號中間的運算子，移除原來的運算子，並消除原本右括號對應的左括號。完整步驟如下：

如此一來，中序式a + b * c - d / e就轉成後序式a b c * + d e / -了！

後序式轉中序式

從左邊開始尋找不在括號內的運算子，將找到的運算子移動到其左邊的兩個運算元(或者已被括號的子算式)中間，並加上括號，直到式子已看到最右邊了。以a b c * + d e / -來舉例，完整步驟如下：

如此一來，後序式a b c * + d e / -就轉成中序式( ( a + ( b * c ) ) - ( d / e ) )了！

'''

# Binarytree Module in Python

A binary tree is a data structure in which every node or vertex has atmost two children.

In Python, a binary tree can be represented in different ways with different data structures(dictionary, list) and class representation for a node.

However, binarytree library helps to directly implement a binary tree. It also supports heap and binary search tree(BST). This module does not come pre-installed with Python’s standard utility module. To install it type the below command in the terminal.

pip install binarytree

Creating Node

The node class represents the structure of a particular node in the binary tree. The attributes of this class are values, left, right.

Syntax: binarytree.Node(value, left=None, right=None)

Parameters:

value: Contains the data for a node. This value must be number.

left: Conatins the details of left node child.

right: Contains details of the right node child

Note: If left or right child node is not an instance of binarytree.Node class then binarytree.exceptions.NodeTypeError is raised and if the node value is not a number then binarytree.exceptions.NodeValueError is raised.

'''

# This is ch06-tree.py by 0000000XXX (學號) YYYYYY(姓名) on 2020/06/05

# This is 展示 Bibary tree (二元樹)的實作

# 程式的前兩行務必註明：學號、姓名、題號、及用途

from binarytree import Node

root = Node(3)

root.left = Node(6)

root.right = Node(8)

# Getting binary tree

print('Binary tree (二元樹) :', root)

# Getting list of nodes

print('List of nodes (列出節點) :', list(root))

# Getting inorder of nodes

print('Inorder of nodes (節點的中序) :', root.inorder)

# Checking tree properties

print('Size of tree (樹的大小) :', root.size)

print('Height of tree (樹的高度):', root.height)

# Get all properties at once

print('Properties of tree (樹的屬性): \n', root.properties)

'''

作業6：

# EX6-1. 從一個 list 的 10 個數值依序填滿建立一個二元樹，並印出其值。

# 使用 from binarytree import build

# EX6-2. 輸入樹高，建立一個亂數數值的二元樹，並印出其值。

# 使用 from binarytree import tree

# EX6-3. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import bst

# EX6-4. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import heap

# EX6-5. 使用前序追蹤該二元樹 (MLR)

# EX6-6. 使用中序追蹤該二元樹 (LMR)

# EX6-7. 使用後序追蹤該二元樹 (LRM)

'''

# This is ch06-tree.py by 0000000XXX (學號) YYYYYY(姓名) on 2020/06/05

# This is 展示 Bibary tree (二元樹)的實作

# 程式的前兩行務必註明：學號、姓名、題號、及用途

# EX6-2. 輸入樹高，建立一個亂數數值的二元樹，並印出其值。

# 使用 from binarytree import tree

'''

Build a random binary tree

tree() generates a random binary tree and returns its root node.

Syntax: binarytree.tree(height=3, is_perfect=False)

Parameters:

height: It is the height of the tree and its value can be between the range 0-9 (inclusive)

is_perfect: If set True a perfect binary is created.

Returns: Root node of the binary tree.

'''

from binarytree import tree

print ('Ex6-2 \n')

# Create a random binary

# tree of any height

root3 = tree(height = 3,

is_perfect = True)

print("Perfect binary tree of given height :")

print(root3)

# 建立樹的節點

from binarytree import Node

root = Node(3)

root.left = Node(6)

root.right = Node(8)

root[1] = Node(5)

root[1].left = Node(15)

root[1].right = Node(7)

root[2] = Node(9)

root[2].left = Node(10)

root[2].right = Node(2)

for i in range (0,3,1):

print('%d \n' % i)

print (root[i])

print (root[i].left)

print (root[i].right)

樹 Tree

Tree (CH06)

電腦是怎麼進行四則運算的？