未分類

Valid Parentheses

Go, LeetCode, Stack, String

Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

提示 解題應用
Stack LinkedList
String 觀查規律

Default:

1
2
3
func isValid(s string) bool {
}

解答思路:

剛看到這題時就相當直覺的要用stack來做，如果曾經碰過用程式來跑四則運算的話，那一定會碰上先乘除後加減還有括號的問題，那時就是用stack來做括號及順序的匹配，果不其然和我們想的一模一樣，只是寫的時候才發現和一開始的稍有出入，原本是想先將所有字串的字元一一完全塞入stack之後再來判斷，不過這麼一來就要一一拿出再考慮似乎繞圈子，倒不如邊塞的時候就要邊做判斷，只是記得要記錄前一個你塞入的字元是什麼，才有辦法在下一個來時做判斷是否匹配。因為不曉得stack究竟會多長，所以就用LinkedList來實做，不然其實array會更簡單。

程式碼解說:

因為不曉得長度，所以用節點的方式來實做，不過因為stack的操作都是在第一個節頭，所以就不用像一般的LinkedList一樣需要創一個頭、尾節點來達到對每一節點操作的一致性

1
2
3
4
type stackNode struct {
	s    string
	next *stackNode
}

在一一的將字串中的字元製成節點時，一邊要用tmp來儲存上一個節點中的字元以方便與下一字元做比較，如果不相同就將其做成節點塞入LinkedList並將top重新指向新節點，而上一個與目前字元的括號匹配的話就將stack中上一個字元所做的節點拿出來，同樣的這邊我並沒有去將該點的記憶體空間給釋放掉，所以也可以再加一行去處理，記得再將節點拿出來之後，因為tmp已經與目前的字元匹配了，所以要賦予tmp新的值，也就是在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
var top *stackNode
var tmp string
var str string
for _, v := range s {
	str = string(v)
	if tmp == "(" && str == ")" {
		top = top.next
		if top != nil {
			tmp = top.s
		}
	} else if tmp == "[" && str == "]" {
		top = top.next
		if top != nil {
			tmp = top.s
		}
	} else if tmp == "{" && str == "}" {
		top = top.next
		if top != nil {
			tmp = top.s
		}
	} else {
		tmp = str
		node := &stackNode{}
		node.s = str
		node.next = top
		top = node
	}
}

最後只要判斷這個stack也就是top所指向的第一個節點，如果全數匹配的話那麼應該會被一一拿出LinkedList之外，而top就會是空的，有剩餘的點就表示括號的匹配不符回傳false

1
2
3
4
if top != nil {
	return false
}
return true

完整程式碼:

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
37
38
type stackNode struct {
	s    string
	next *stackNode
}
func isValid(s string) bool {
	var top *stackNode
	var tmp string
	var str string
	for _, v := range s {
		str = string(v)
		if tmp == "(" && str == ")" {
			top = top.next
			if top != nil {
				tmp = top.s
			}
		} else if tmp == "[" && str == "]" {
			top = top.next
			if top != nil {
				tmp = top.s
			}
		} else if tmp == "{" && str == "}" {
			top = top.next
			if top != nil {
				tmp = top.s
			}
		} else {
			tmp = str
			node := &stackNode{}
			node.s = str
			node.next = top
			top = node
		}
	}
	if top != nil {
		return false
	}
	return true
}

總結:

字串中若字元與字元有兩兩相互匹配，且存在著先進後出的關係(例: {[()]} , 四則運算的前、中、後綴表達式)就用Stack來做儲存。

分享到