From 947da6a7c9dd61dad5bc8fa6d84bb0ed590c251b Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 3 Jan 2019 19:58:31 -0600
Subject: Check bracket done!

Implementation isn't difficult since I worked the algo out in Java and
Python already. I tried to use VS Code to write this but in the end
decided to stick with Eclipse. Doing this in VS Code may not be worth
the investment.---
 Sources/DataStructure.cpp | 115 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)
 create mode 100644 Sources/DataStructure.cpp

(limited to 'Sources')

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
new file mode 100644
index 0000000..1360ef5
--- /dev/null
+++ b/Sources/DataStructure.cpp
@@ -0,0 +1,115 @@
+#include <iostream>
+#include <stack>
+#include <algorithm>
+#include <vector>
+//#include <gtest/gtest.h>
+
+using std::string;
+using std::stack;
+
+const std::vector<char> brackets = {'[',']','(',')','{','}'};
+
+static string checkBracket(string exp) {
+    stack<char> charStack;
+    int unmatchedOpeningBracket = 0;
+    int count = 0;
+    for (int i = 0; i < exp.length(); i++) {
+        char c = exp[i];
+        if (!(std::find(brackets.begin(), brackets.end(), c) !=brackets.end())) {
+            count = count + 1;
+            continue;
+        }
+
+        if (c == '[' || c == '(' || c == '{') {
+            charStack.push(c);
+            count = count + 1;
+            unmatchedOpeningBracket = count;
+        } else {
+            if (charStack.empty())
+                return std::to_string(i+1);
+            char top = charStack.top();
+            charStack.pop();
+            if ((top == '[' && c != ']') || (top == '(' && c != ')') || (top == '{' && c != '}')) {
+                return std::to_string(i+1);
+            } else {
+                unmatchedOpeningBracket = unmatchedOpeningBracket - 1;
+            }
+            count = count + 1;
+        }
+    }
+    if (charStack.empty())
+        return "Success";
+    else if (unmatchedOpeningBracket > 0) {
+        return std::to_string(unmatchedOpeningBracket);
+    }
+    return std::to_string(count);
+}
+
+//TEST(CheckBracket, t1) {
+//    string exp = "[]";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t2) {
+//    string exp = "{}[]";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t3) {
+//    string exp = "[()]";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t4) {
+//    string exp = "(())";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t5) {
+//    string exp = "{[]}()";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t6) {
+//    string exp = "{";
+//    ASSERT_EQ("1", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t7) {
+//    string exp = "{[}";
+//    ASSERT_EQ("3", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t8) {
+//    string exp = "foo(bar);";
+//    ASSERT_EQ("Success", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t9) {
+//    string exp = "foo(bar[i);";
+//    ASSERT_EQ("10", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t10) {
+//    string exp = "[](()";
+//    ASSERT_EQ("3", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t11) {
+//    string exp = "{[}haha";
+//    ASSERT_EQ("3", checkBracket(exp));
+//}
+//
+//TEST(CheckBracket, t12) {
+//    string exp = "haha{[}";
+//    ASSERT_EQ("7", checkBracket(exp));
+//}
+
+int main() {
+    std::string text;
+    getline(std::cin, text);
+
+    std::cout << checkBracket(text) << '\n';
+
+    return 0;
+}
-- 
cgit v1.2.3