0224 solved.

liuyubobobo · liuyubobobo · commit 6143c5dfd4fd · 2018-09-03T16:06:15.000-07:00
diff --git a/0224-Basic-Calculator/cpp-0224/CMakeLists.txt b/0224-Basic-Calculator/cpp-0224/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(cpp_0224)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(cpp_0224 ${SOURCE_FILES})
diff --git a/0224-Basic-Calculator/cpp-0224/main.cpp b/0224-Basic-Calculator/cpp-0224/main.cpp
@@ -0,0 +1,87 @@
+/// Source : https://leetcode.com/problems/basic-calculator/description/
+/// Author : liuyubobobo
+/// Time   : 2018-09-03
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+
+using namespace std;
+
+
+/// Two Stacks
+/// Shunting-Yard Algorithms: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    int calculate(string s) {
+
+        vector<int> nums;
+        vector<char> ops;
+
+        for(int i = 0; i < s.size(); ){
+            if(s[i] == '+' || s[i] == '-' || s[i] == '(')
+                ops.push_back(s[i++]);
+            else if(s[i] == ')'){
+                assert(!ops.empty() && ops.back() == '(');
+                ops.pop_back();
+                i ++;
+
+                cal(nums, ops);
+            }
+            else if(isdigit(s[i])){
+
+                int num = s[i] - '0';
+                int j;
+                for(j = i + 1; j < s.size() && isdigit(s[j]); j ++)
+                    num = num * 10 + (s[j] - '0');
+                i = j;
+
+                nums.push_back(num);
+                cal(nums, ops);
+            }
+            else
+                i ++;
+
+//            Solution::print_vec(nums);
+//            Solution::print_vec(ops);
+//            cout << endl;
+        }
+
+        assert(nums.size() == 1);
+        return nums.back();
+    }
+
+private:
+    void cal(vector<int>& nums, vector<char>& ops){
+
+        if(!ops.empty() && (ops.back() == '+' || ops.back() == '-')){
+            int second = nums.back();
+            nums.pop_back();
+            assert(!nums.empty());
+            int first = nums.back();
+            nums.pop_back();
+            nums.push_back(ops.back() == '+' ? (first + second) : (first - second));
+            ops.pop_back();
+        }
+    }
+
+    template<typename T>
+    static void print_vec(const vector<T>& vec){
+        for(int i = 0; i < vec.size(); i ++)
+            cout << vec[i] << " ";
+        cout << endl;
+    }
+};
+
+
+int main() {
+
+    cout << Solution().calculate("1 + 1") << endl; // 2
+    cout << Solution().calculate(" 2-1 + 2 ") << endl; // 3
+    cout << Solution().calculate("(1+(4+5+2)-3)+(6+8)") << endl; // 23
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -205,6 +205,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 222 | [Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/description/) | [无] | [C++](0222-Count-Complete-Tree-Nodes/cpp-0222/) | | |
 | | | | | | |
+| 224 | [Basic Calculator](https://leetcode.com/problems/basic-calculator/description/) | [无] | [C++](0224-Basic-Calculator/cpp-0224/) | | |
+| | | | | | |
 | 226 | [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/description/) | [solution](https://leetcode.com/problems/invert-binary-tree/solution/) | [C++](0226-Invert-Binary-Tree/cpp-0226/) | [Java](0226-Invert-Binary-Tree/java-0226/src/) | |
 | | | | | | |
 | 230 | [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/) | [无] | [C++](0230-Kth-Smallest-Element-in-a-BST/cpp-0230/) | | |
