Merge pull request soapyigu#281 from pepsikirk/master

soapyigu · web-flow · commit c65138d5a8dc · 2020-01-20T16:19:28.000-08:00
[Stack] Add a solution to Basic Calculator
diff --git a/README.md b/README.md
@@ -174,6 +174,7 @@
 [Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)| [Swift](./Stack/BinarySearchTreeIterator.swift)| Medium| O(n)| O(n)|
 [Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)| [Swift](./Stack/PostorderTraversal.swift)| Hard| O(n)| O(n)|
 [Decode String](https://leetcode.com/problems/decode-string/)| [Swift](./Stack/DecodeString.swift)| Medium| O(n)| O(n)|
+[Basic Calculator](https://leetcode.com/problems/basic-calculator/)| [Swift](./Stack/BasicCalculator.swift)| Hard| O(n)| O(n)|
 
 ## Queue
 | Title | Solution | Difficulty | Time | Space |
@@ -689,7 +690,7 @@
 |		|	227	|	[Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/)	|	Medium	|
 |	[Swift](./Tree/InvertBinaryTree.swift)	|	226	|	[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)	| Easy	|
 |		|	225	|	[Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)	| Easy	|
-|		|	224	|	[Basic Calculator](https://leetcode.com/problems/basic-calculator/)	|	Hard	|
+|	[Swift](./Stack/BasicCalculator.swift)	|	224	|	[Basic Calculator](https://leetcode.com/problems/basic-calculator/)	|	Hard	|
 |	[Swift](./Math/RectangleArea.swift)	|	223	|	[Rectangle Area](https://leetcode.com/problems/rectangle-area/)	| Easy	|
 |		|	222	|	[Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)	|	Medium	|
 |	[Swift](./DP/MaximalSquare.swift)	|	221	|	[Maximal Square](https://leetcode.com/problems/maximal-square/)	|	Medium	|
diff --git a/Stack/BasicCalculator.swift b/Stack/BasicCalculator.swift
@@ -0,0 +1,33 @@
+/**
+ * Question Link: https://leetcode.com/problems/basic-calculator/
+ * Primary idea: Use a stack to save sign, then determines whether sign inversion is currently required
+ * Time Complexity: O(n), Space Complexity: O(n)
+ */
+
+class BasicCalculator {
+    func calculate(_ s: String) -> Int {
+        var result = 0
+        var num = 0
+        var sign = 1
+        var stack = [sign]
+        
+        for char in s {
+            switch char {
+            case "+", "-":
+                result += num * sign
+                sign = stack.last! * (char == "+" ? 1 : -1)
+                num = 0
+            case "(":
+                stack.append(sign)
+            case ")":
+                stack.removeLast()
+            case " ":
+                break
+            default:
+                num = num * 10 + char.wholeNumberValue!
+            }
+        }
+        
+        return result + num * sign
+    }
+}
