Node * create(Node * root, int I, int J, string str)
{
if (I == J) { root -> data =str[I]; root -> left=NULL; root -> right=NULL; }
int i = 0, j = 0, k = 0, l = 0;
//// to store the data of root
string val;
for (i = I; i < J; i++) {
if (str[i] == '(') break;
val.push_back(str[i]);
}
root -> data = stoi(val);
stack < char > st;
for (j = i; j < J; j++) {
if (str[j] == '(') st.push(str[j]);
else if (str[j] == ')') st.pop();
if (st.empty()) break;
}
for (l = j + 1; l < J; l++) {
if (str[l] == '(') st.push(str[l]);
else if (str[l] == ')') st.pop();
if (st.empty()) break;
}
k = j + 1;
if (j - i == 2) root -> left -> data = str[i + 1];
else
root -> left = create(root -> left, i + 1, j - 1, str);
if (l == k) root -> right=NULL;
else if (l - k == 2) root -> right -> data = str[k + 1];
else
root -> right = create(root -> right, k + 1, l - 1, str);
return root;
}
Node * treeFromString(string str){
Node * p = create(p, 0, str.size() - 1, str);
return p;
}
这里我初始化了变量I, j, k, l来跟踪字符串中的左子括号和右子括号。I, J是一个特定递归激活记录的节点范围。
我假设您解析了一些表达式，通过您的代码我预实现了它。
我只是为下面的表达式实现构建一个树:
expression: |<symbol>| <integer> '(' <expression> ')' '('<expression>')'
symbol : any C++ `char` single byte character.
integer : any C++ valid int type value.
#include <iostream>
#include <string>
#include <string_view> // C++17 std::string_view
#include <charconv> // C++17 std::from_chars.
#include <cassert>
//simulate Node class
struct Node
{
Node *left, *right;
int data;
};
//1. use string_view instead of triple I, J, std::string.
//2. First argument Node* root - needn't. It should be local variable.
Node * create(std::string_view str)
{
assert(!str.empty());
if (str.size() == 1)
{
Node* root = new Node; //-> YOU should allocate a memory for root.
root -> data =str[0];
root -> left=nullptr; // use nullptr instead of NULL for c++11 or later.
root -> right=nullptr;
return root; // exit needed!
}
Node* root = new Node;
root->left = nullptr;
root->right = nullptr;
root->data = 0;
//// to store the data of root
//2. THERE NEED take an integer until first '(' symbol.
{
std::size_t i = 0;
while (i < str.size() && str[i] != '(' )
++i;
// str[0 .. i) - interval is an integer.
int val = 0;
(void)std::from_chars(str.data(), str.data() + i, val); // FOR simplifity don't check validness of conversation.
str.remove_prefix(i);
root->data = val;
}
//3. SKIP balanced '(' and ')'
/*stack < char > st;
for (j = i; j < J; j++) {
if (str[j] == '(') st.push(str[j]);
else if (str[j] == ')') st.pop();
if (st.empty()) break;
}
* */
/** we can implement it another way */
assert(!str.empty() && str[0] == '(' );
std::string_view within_bracket;
{
int balanced_brackets = 0;
std::size_t i = 0;
while (i < str.size())
{
if (str[i] == '(') ++ balanced_brackets;
else if (str[i] == ')' ) --balanced_brackets;
i++;
if (balanced_brackets == 0)
break;
}
assert (i > 0 && str[ i - 1 ] == ')' );
// 0 1 2 3
// str[0..i) - is '(' ... ')' symbols.
within_bracket = std::string_view(str.data() + 1, i - 2);
str.remove_prefix(i);
}
/****4. THIS second balanced bracket check */
std::string_view second_within_bracket;
/*
for (l = j + 1; l < J; l++) {
if (str[l] == '(') st.push(str[l]);
else if (str[l] == ')') st.pop();
if (st.empty()) break;
}
k = j + 1;
*/
assert(!str.empty() && str[0] == '(' );
// ========== second balanced brackets check ==========
{
std::size_t i = 0;
int balanced_brackets = 0;
while (i < str.size())
{
if (str[i] == '(') ++ balanced_brackets;
else if (str[i] == ')' ) --balanced_brackets;
i++;
if (balanced_brackets == 0)
break;
}
// 0 1 2 3
// str[0..i) - is '(' ... ')' symbols.
second_within_bracket = std::string_view(str.data() + 1, i - 2);
str.remove_prefix(i);
}
//================================
/*
if (j - i == 2) root -> left -> data = str[i + 1];
else
root -> left = create(i + 1, j - 1, str);
if (l == k) root -> right=NULL;
else if (l - k == 2) root -> right -> data = str[k + 1];
else
root -> right = create(root -> right, k + 1, l - 1, str);
*/
root->left = create(within_bracket);
root->right = create(second_within_bracket);
return root;
}
Node * treeFromString(std::string_view str){
Node * p = create(str);
return p;
}
void printTree(Node* root, int level = 0)
{
if (root==nullptr) return;
for (int i= 0; i < level; ++i) std::cout << "--";
std::cout << " data = " << root->data << std::endl;
printTree(root->left, level + 1);
printTree(root->right, level + 1);
}
int main(){
std::string str = "12(8(7)(5))(9(3)(2(1)(8)))";
Node * expr = treeFromString(str);
printTree(expr);
}
godbold输出:
Program returned: 0
data = 12
-- data = 8
---- data = 55
---- data = 53
-- data = 9
---- data = 51
---- data = 2
------ data = 49
------ data = 56
这个答案有点不同，它假设您正在从字符串加载整数值树，可以从文件加载。下次你问一个关于代码的问题时，你能解释一下代码是做什么的吗?猜测确实需要一些时间和精力。
我从Khurshid Normuradov的回答中重用了main()和PrintTree()函数。我希望他不会介意。
我冒昧地添加了现代c++编码技术，因为这个问题被标记为c++17，所以你得到的是一个c++17的例子。
#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <string_view>
struct Node {
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
int value = 0;
};
std::unique_ptr<Node> treeFromString(std::string_view str) {
std::cout << "treeFromString("" << str << "")n";
if (str.empty()) return {};
auto node = std::make_unique<Node>();
// extract an int
auto pos = str.find_first_not_of("0123456789");
auto val = str.substr(0, pos);
// optional: std::stoi() would throw anyway in this case
if (val.empty())
throw std::runtime_error("invalid value in expression");
node->value = std::stoi(std::string{val});
if (val.length() == str.length()) return node;
str = str.substr(val.length());
// Both left/right parsing are similar and use this
// common subroutine.
// expects parens delimited string as input.
// param str in: str string to parse from
// out: whatever's left to parse
// returns string content within parens, parens not included.
auto extract_parens_contents = [](std::string_view& str) {
// right here would be the perfect place to insert code to skip
// whitespace if you ever needed to do that.
// find parens extent
int parens = 0;
auto parens_end =
std::find_if(str.begin(), str.end(), [&parens](char c) {
parens += (c == '(') - (c == ')');
return (parens == 0);
});
if (parens_end == str.end())
throw std::runtime_error("unbalanced parens in expression");
// extract result
auto result = std::string_view(
str.begin() + 1, std::distance(str.begin() + 1, parens_end));
// remove spent bytes from input stream
str = std::string_view(
parens_end + 1,
str.length() - std::distance(str.begin(), parens_end + 1));
return result;
};
node->left = treeFromString(extract_parens_contents(str));
node->right = treeFromString(extract_parens_contents(str));
return node;
}
// special thanks to user Khurshid Normuradov, who originally wrote the two functions below.
// it would be difficult to writing something that would be any better for the
// intended purpose.
void printTree(Node* root, int level = 0) {
if (root == nullptr) return;
for (int i = 0; i < level; ++i) std::cout << "--";
std::cout << " data = " << root->value << std::endl;
printTree(root->left.get(), level + 1);
printTree(root->right.get(), level + 1);
}
int main() {
std::string str = "12(8(7)(5))(9(3)(2(1)(8)))";
auto expr = treeFromString(str);
printTree(expr.get());
}
您可以在这里使用代码:https://godbolt.org/z/ch3zv5KTT