未分類

Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

For examples:

1
2
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
提示 解題應用
Stack LinkedList

Default:

1
2
3
func evalRPN(tokens []string) int {
}

解答思路:

這題要你將已經被逆波蘭表示法拆解的算式還原回去並計算結果,而RPN其實就是資料結構所提到堆疊運用的四則運算後置式(運算子在後頭),最困難的部分都已經拆解好要再還原算式以計算結果就非常容易,遍歷已拆解的算式,只要碰到運算元就放入stack之中,碰到運算子才從stack中取出兩個運算元做計算,並再將得到的結果再次放回stack,最後遍歷結束後在stack中唯一一個剩下的運算元就是我們要的結果。

程式碼解說:

因為stack是採用LinkedList的方式實作,所以一開始就先定義好節點的結構,包含其值與下一個節點的位置

1
2
3
4
type Node struct {
Val int
Next *Node
}

接著就開始還原算式並計算結果,一開始先遍歷已拆解的字串,碰到運算子就從stack中取出兩個運算元做計算(第一個取出的運算元在運算子後面,第二個在前面),並根據運算子的符號做對應的計算,再將計算結果包成stack的頭節點再次放回stack之中,而如果是碰到運算元則直接包裝成頭節點放入stack之中(記得要將字串轉成數字,後續取出才可以拿來計算),最後遍歷結束後在stack中唯一一個剩下的運算元(也就是頭節點)就是我們要的結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func evalRPN(tokens []string) int {
var tmp int
var numFront int
var numBack int
var top *Node
var newNode *Node
for _, v := range tokens {
if v == "+" || v == "-" || v == "*" || v == "/" {
numBack = top.Val
top = top.Next
numFront = top.Val
top = top.Next
switch v {
case "+":
tmp = numFront + numBack
case "-":
tmp = numFront - numBack
case "*":
tmp = numFront * numBack
case "/":
tmp = numFront / numBack
}
newNode = &Node{tmp, top}
top = newNode
} else {
val, _ := strconv.Atoi(v)
newNode = &Node{val, top}
top = newNode
}
}
return top.Val
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type Node struct {
Val int
Next *Node
}
func evalRPN(tokens []string) int {
var tmp int
var numFront int
var numBack int
var top *Node
var newNode *Node
for _, v := range tokens {
if v == "+" || v == "-" || v == "*" || v == "/" {
numBack = top.Val
top = top.Next
numFront = top.Val
top = top.Next
switch v {
case "+":
tmp = numFront + numBack
case "-":
tmp = numFront - numBack
case "*":
tmp = numFront * numBack
case "/":
tmp = numFront / numBack
}
newNode = &Node{tmp, top}
top = newNode
} else {
val, _ := strconv.Atoi(v)
newNode = &Node{val, top}
top = newNode
}
}
return top.Val
}

總結:

要將已經被RPN逆波蘭表示法拆解的算式還原回去並計算結果,只要遍歷已拆解的算式,只要碰到運算元就放入stack之中,碰到運算子才從stack中取出兩個運算元做計算,並再將得到的結果再次放回stack,最後遍歷結束後在stack中唯一一個剩下的運算元就是我們要的結果。

分享到