未分類

Basic Calculator II

Go, LeetCode, String

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

For examples:

1
2
3
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note:

Do not use the eval built-in library function.

提示 解題應用
String Reverse Polish Notation

Default:

1
2
3
func calculate(s string) int {
}

解答思路:

給一四則運算的算式要求出結果，對於人來說要處理這種一般先乘除後加減的算式(中置式)相當容易，但對程式來說就比較困難，所以就需要先將算式轉化成程式比較容易處理的後置式之後再運算，先前有一篇Evaluate Reverse Polish Notation就是將後置式的結果做運算，總而言之如果要將一般的算式給程式做運算最主要分為兩個步驟，第一個就是將中置式轉為後置式，先遍歷原本的算式，碰到運算元就直接輸出，而碰到運算子就放入stack之中，如果stack已經有運算子在裡頭就與其比較優先順序(*,/的優先順序相同且比+,-大)，如果stack的比較大或相同就不斷的輸出，直到出現優先順序比較小的為止才放入stack，待算式轉為後置式接下來就是第二個步驟，將後置式的結果做運算(細節可以參考前一篇的實作)，遍歷後置式的算式，只要碰到運算元就放入stack之中，碰到運算子才從stack中取出兩個運算元做計算，並再將得到的結果再次放回stack，最後遍歷結束後在stack中唯一一個剩下的運算元就是我們要的結果。

程式碼解說:

不論是先將中置式轉為後置式，還是將後置式的結果做運算都會用上stack，所以就先定義好stack的結構，這邊是以LinkedList來實作，而一開始就先將算式帶入toRPN轉為後置式，之後其回傳的結果再帶入evalRPN去做運算，最後便能得到算式的答案

1
2
3
4
5
6
7
type StackNode struct {
	Val  string
	Next *StackNode
}
func calculate(s string) int {
	return evalRPN(toRPN(s))
}

要將中置式轉為後置式，先遍歷原本的算式，如果取出的字元為空白字元就跳過，取出的是運算子且為+,-的話，就不斷的將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
33
34
35
36
func toRPN(s string) []string {
	var str string
	var num string
	var RPN []string
	var top *StackNode
	for i, v := range s {
		str = string(v)
		if str == " " {
			continue
		} else if str == "+" || str == "-" {
			for top != nil {
				RPN = append(RPN, top.Val)
				top = top.Next
			}
			top = &StackNode{str, top}
		} else if str == "*" || str == "/" {
			for top != nil && (top.Val == "*" || top.Val == "/") {
				RPN = append(RPN, top.Val)
				top = top.Next
			}
			top = &StackNode{str, top}
		} else {
			num += str
			if i+1 < len(s) && s[i+1] >= 48 && s[i+1] <= 57 {
				continue
			}
			RPN = append(RPN, num)
			num = ""
		}
	}
	for top != nil {
		RPN = append(RPN, top.Val)
		top = top.Next
	}
	return RPN
}

這邊的程式碼與先前求RPN的結果大致相同，詳細的說明可以參考前一篇，唯一的差別是為了與中置式轉為後置式時所使用的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 *StackNode
	var newNode *StackNode
	for _, v := range tokens {
		if v == "+" || v == "-" || v == "*" || v == "/" {
			numBack, _ = strconv.Atoi(top.Val)
			top = top.Next
			numFront, _ = strconv.Atoi(top.Val)
			top = top.Next
			switch v {
			case "+":
				tmp = numFront + numBack
			case "-":
				tmp = numFront - numBack
			case "*":
				tmp = numFront * numBack
			case "/":
				tmp = numFront / numBack
			}
			newNode = &StackNode{strconv.Itoa(tmp), top}
			top = newNode
		} else {
			newNode = &StackNode{v, top}
			top = newNode
		}
	}
	tmp, _ = strconv.Atoi(top.Val)
	return tmp
}

完整程式碼:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
type StackNode struct {
	Val  string
	Next *StackNode
}
func calculate(s string) int {
	return evalRPN(toRPN(s))
}
func toRPN(s string) []string {
	var str string
	var num string
	var RPN []string
	var top *StackNode
	for i, v := range s {
		str = string(v)
		if str == " " {
			continue
		} else if str == "+" || str == "-" {
			for top != nil {
				RPN = append(RPN, top.Val)
				top = top.Next
			}
			top = &StackNode{str, top}
		} else if str == "*" || str == "/" {
			for top != nil && (top.Val == "*" || top.Val == "/") {
				RPN = append(RPN, top.Val)
				top = top.Next
			}
			top = &StackNode{str, top}
		} else {
			num += str
			if i+1 < len(s) && s[i+1] >= 48 && s[i+1] <= 57 {
				continue
			}
			RPN = append(RPN, num)
			num = ""
		}
	}
	for top != nil {
		RPN = append(RPN, top.Val)
		top = top.Next
	}
	return RPN
}
func evalRPN(tokens []string) int {
	var tmp int
	var numFront int
	var numBack int
	var top *StackNode
	var newNode *StackNode
	for _, v := range tokens {
		if v == "+" || v == "-" || v == "*" || v == "/" {
			numBack, _ = strconv.Atoi(top.Val)
			top = top.Next
			numFront, _ = strconv.Atoi(top.Val)
			top = top.Next
			switch v {
			case "+":
				tmp = numFront + numBack
			case "-":
				tmp = numFront - numBack
			case "*":
				tmp = numFront * numBack
			case "/":
				tmp = numFront / numBack
			}
			newNode = &StackNode{strconv.Itoa(tmp), top}
			top = newNode
		} else {
			newNode = &StackNode{v, top}
			top = newNode
		}
	}
	tmp, _ = strconv.Atoi(top.Val)
	return tmp
}

總結:

要求出四則運算算式(中置式)的結果最主要分為兩個步驟，第一個就是將中置式轉為後置式(RPN)，遍歷原本的算式，碰到運算元就直接輸出，而碰到運算子就與stack裡的運算子比較優先順序，如果stack的比較大或相同就不斷的輸出，直到出現優先順序比較小的為止才放入stack，待算式轉為後置式接下來就是第二個步驟將後置式的結果做運算，遍歷後置式的算式，只要碰到運算元就放入stack之中，碰到運算子才從stack中取出兩個運算元做計算，並再將得到的結果再次放回stack，最後遍歷結束後在stack中唯一一個剩下的運算元就是我們要的結果。

分享到