diff options
| -rw-r--r-- | Sources/DataStructure.cpp | 185 |
1 files changed, 90 insertions, 95 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 1360ef5..b82f908 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,115 +1,110 @@ #include <iostream> -#include <stack> +#include <queue> #include <algorithm> #include <vector> //#include <gtest/gtest.h> -using std::string; -using std::stack; +using std::vector; +using std::queue; -const std::vector<char> brackets = {'[',']','(',')','{','}'}; +class Node; -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; - } +class Node { +public: + int key; + Node *parent; + vector<Node *> children; - 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); + Node() { + this->parent = NULL; + } + + void setParent(Node *theParent) { + parent = theParent; + parent->children.push_back(this); + } + + vector<Node *> getChildren() { + return children; + } + + void setKey(int theKey) { + key = theKey; + } +}; + +int treeLevelCounter(vector<Node> &nodes, int rootIndex) { + int levelCounter = 1; + queue<Node *> q; + int popCount = 0; + int childrenCount = nodes[rootIndex].getChildren().size(); + int grandChildrenCount = 0; + for (int i = 0; i < childrenCount; i++) { + q.push(nodes[rootIndex].getChildren()[i]); + } + while (!q.empty()) { + if (popCount < childrenCount) { + Node *n = q.front(); + q.pop(); + int i = n->children.size(); + if (i != 0) { + for (int j = 0; j < i; j++) { + q.push(n->children[j]); + } + } + grandChildrenCount = grandChildrenCount + i; + popCount = popCount + 1; + } else { + popCount = 0; + childrenCount = grandChildrenCount; + grandChildrenCount = 0; + levelCounter = levelCounter + 1; + } + } + return levelCounter + 1; +} +int getHeight(vector<int> &a) { + vector<Node> nodes; + nodes.resize(a.size()); + int rootIndex = 0; + for (int i = 0; i < a.size(); i++) { + int parentIndex = a[i]; + nodes[i].setKey(i); + if (parentIndex == -1) { + rootIndex = i; + } else { + nodes[i].setParent(&nodes[parentIndex]); + } + } + return treeLevelCounter(nodes, rootIndex); } -//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(GetTreeHeight, t1) { +// vector<int> a = {4, -1, 4, 1, 1}; +// ASSERT_EQ(3, getHeight(a)); //} // -//TEST(CheckBracket, t4) { -// string exp = "(())"; -// ASSERT_EQ("Success", checkBracket(exp)); +//TEST(GetTreeHeight, t2) { +// vector<int> a = {-1, 0, 4, 0, 3}; +// ASSERT_EQ(4, getHeight(a)); //} // -//TEST(CheckBracket, t5) { -// string exp = "{[]}()"; -// ASSERT_EQ("Success", checkBracket(exp)); +//TEST(GetTreeHeight, t3) { +// vector<int> a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1}; +// ASSERT_EQ(4, getHeight(a)); //} // -//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)); +//TEST(GetTreeHeight, t4) { +// vector<int> a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5}; +// ASSERT_EQ(6, getHeight(a)); //} int main() { - std::string text; - getline(std::cin, text); - - std::cout << checkBracket(text) << '\n'; - - return 0; + size_t an; + std::cin >> an; + vector<int> a(an); + for (size_t i = 0; i < an; i++) { + std::cin >> a[i]; + } + std::cout << getHeight(a) << std::endl; } |