basic_calculator_II

hitzzc · hitzzc · commit bde3c2b6ca94 · 2016-10-17T21:07:52.000+08:00
diff --git a/README.md b/README.md
@@ -183,7 +183,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [224. Basic Calculator](https://github.com/hitzzc/go-leetcode/tree/master/basic_calculator)
 #### [225. Implement Stack using Queues](https://github.com/hitzzc/go-leetcode/tree/master/implement_stack_using_queues)
 #### [226. Invert Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/invert_binary_tree)
-
+#### [227. Basic Calculator II](https://github.com/hitzzc/go-leetcode/tree/master/basic_calculator_II)
 
 
 
diff --git a/basic_calculator_II/basic_calculator_II.go b/basic_calculator_II/basic_calculator_II.go
@@ -0,0 +1,57 @@
+package basic_calculator_II
+
+func calculate(s string) int {
+	numStack := []int{}
+	opStack := []byte{}
+	for i := 0; i < len(s); i++ {
+		if s[i] >= '0' && s[i] <= '9' {
+			num := 0
+			for ; i < len(s) && s[i] >= '0' && s[i] <= '9'; i++ {
+				num = 10*num + int(s[i]-'0')
+			}
+			numStack = append(numStack, num)
+			i--
+		} else if s[i] == ' ' {
+			continue
+		} else {
+			for len(opStack) != 0 && priority(opStack[len(opStack)-1]) >= priority(s[i]) {
+				num := operate(numStack[len(numStack)-2], numStack[len(numStack)-1], opStack[len(opStack)-1])
+				numStack[len(numStack)-2] = num
+				numStack = numStack[:len(numStack)-1]
+				opStack = opStack[:len(opStack)-1]
+			}
+			opStack = append(opStack, s[i])
+		}
+	}
+	for len(opStack) != 0 {
+		num := operate(numStack[len(numStack)-2], numStack[len(numStack)-1], opStack[len(opStack)-1])
+		numStack[len(numStack)-2] = num
+		numStack = numStack[:len(numStack)-1]
+		opStack = opStack[:len(opStack)-1]
+	}
+	return numStack[0]
+}
+
+func priority(op byte) int {
+	switch op {
+	case '*', '/':
+		return 2
+	case '+', '-':
+		return 1
+	}
+	return 0
+}
+
+func operate(i, j int, op byte) int {
+	switch op {
+	case '+':
+		return i + j
+	case '-':
+		return i - j
+	case '*':
+		return i * j
+	case '/':
+		return i / j
+	}
+	return 0
+}
