未分類

Evaluate Reverse Polish Notation

Go, LeetCode, Stack

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中唯一一個剩下的運算元就是我們要的結果。

分享到