Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4.  
  5. using namespace std;
  6. typedef char type;
  7.  
  8. struct elem{
  9. elem* l = nullptr;
  10. elem* r = nullptr;
  11. type atom;
  12. };
  13.  
  14.  
  15. void make_space(string& str){
  16. for (int i = 0; i < str.size(); i++){
  17. if (str[i + 1] != ' ' && str[i] != ' ') {
  18. str.insert(i + 1, " ");
  19. i++;
  20. }
  21. }
  22. }
  23.  
  24.  
  25. elem* create_left(elem* bin_tree, type atom){
  26. elem* push = new elem;
  27.  
  28. bin_tree->l = push;
  29. bin_tree = bin_tree->l;
  30. bin_tree->atom = atom;
  31.  
  32. return bin_tree;
  33. }
  34.  
  35.  
  36. elem* create_right(elem* bin_tree, type atom){
  37. elem* push = new elem;
  38.  
  39. bin_tree->r = push;
  40. bin_tree = bin_tree->r;
  41. bin_tree->atom = atom;
  42.  
  43. return bin_tree;
  44. }
  45.  
  46. //(a (b (d #(h # #))(e # #))(c (f (i # #)(j # #))(g #(k (l # #) #))))
  47. elem* create_bin_tree(elem* tree, istringstream& stream, bool init) {
  48. if (init){
  49. tree = new elem;
  50. }
  51.  
  52. char x;
  53. elem* cur = tree;
  54. stream >> x;
  55.  
  56. if (x == '('){
  57. stream >> x;
  58. if (init){
  59. tree->atom = x;
  60. init = false;
  61. create_bin_tree(tree, stream, init);
  62. }else {
  63. tree = create_left(cur, x);
  64. create_bin_tree(tree, stream, init);
  65. }
  66. }
  67. if (x == '#'){
  68. stream >> x;
  69. if (x == '('){
  70. stream >> x;
  71. tree = create_right(cur, x);
  72. create_bin_tree(tree, stream, init);
  73. }
  74. }
  75.  
  76. stream >> x;
  77. if (x == ')'){
  78. return nullptr;
  79. }
  80. if (x == '('){
  81. stream >> x;
  82. tree = create_right(cur, x);
  83. create_bin_tree(tree, stream, init);
  84. }
  85. stream >> x;
  86. return cur;
  87. }
  88.  
  89.  
  90. bool check_ident(elem* tree1, elem* tree2){
  91. if (tree1 && tree2)
  92. {
  93. if(tree1->atom == tree2->atom)
  94. return check_ident(tree1->l, tree2->r)&&check_ident(tree1->r, tree2->l);
  95. else
  96. return false;
  97. }
  98. else return !(tree1 == nullptr xor tree2 == nullptr);
  99. }
  100.  
  101.  
  102. void destroy(elem*& tree){
  103. if (tree != nullptr){
  104. destroy(tree->l);
  105. destroy(tree->r);
  106. delete tree;
  107. tree = nullptr;
  108. }
  109. }
  110.  
  111.  
  112. int main(){
  113. string str_bin_tree1;
  114. char x;
  115. elem* bin_tree1 = nullptr;
  116.  
  117. getline(cin, str_bin_tree1);
  118.  
  119. make_space(str_bin_tree1);
  120. istringstream stream1(str_bin_tree1);
  121.  
  122. bin_tree1 = create_bin_tree(nullptr, stream1, true);
  123.  
  124.  
  125.  
  126. destroy(bin_tree1);
  127. return 0;
  128. }
  129.  
  130. //(a (b (d #(h # #))(e # #))(c (f (i # #)(j # #))(g #(k (l # #) #))))
  131.  
  132. //(a (c (g (k #(l # #))#)(f(j # #)(i # #)))(b (e # #)(d (h # #)#)))
  133.  
  134. /*
  135. *
  136. *
  137. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement