Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node{
  5. bool number;
  6. int value;
  7. node *l, *r;
  8. ///0 +
  9. ///1 -
  10. ///2 *
  11. ///3 /
  12. };
  13. node t[10000];
  14. int gg = 0;
  15. #define tree node *
  16.  
  17. string str;
  18.  
  19. bool check(int l, int r) {
  20. if (l > r) return false;
  21. while(l <= r) {
  22. if (str[l] == ' ') {
  23. l++;
  24. continue;
  25. }
  26. if (str[l] < '0' || str[l] > '9') return false;
  27. l++;
  28. }
  29. return true;
  30. }
  31.  
  32. int get_number(int l, int r) {
  33. if (l > r) return 0;
  34. int ans = 0, j = 1;
  35. while(l <= r) {
  36. if (str[r] == ' ') {
  37. r--;
  38. continue;
  39. }
  40. ans += (str[r] - '0') * j;
  41. j *= 10;
  42. r--;
  43. }
  44. return ans;
  45. }
  46.  
  47. void build(tree t, int l , int r) {
  48. //cout << l << ' ' << r << endl;
  49. if (check(l, r)) {
  50. t->number = true;
  51. t->value = get_number(l, r);
  52. t->l = nullptr;
  53. t->r = nullptr;
  54. return;
  55. }
  56. for(int i = l; i <= r; i++) {
  57. if (str[i] == ' ') continue;
  58. if (str[i] == '+') {
  59. t->r = &t[gg++];
  60. t->l = &t[gg++];
  61. t->number = false;
  62. t->value = 0;
  63. build(t->r, i + 1, r);
  64. build(t->l, l, i - 1);
  65. return;
  66. }
  67. if (str[i] == '-') {
  68. t->r = &t[gg++];
  69. t->l = &t[gg++];
  70. t->number = false;
  71. t->value = 1;
  72. build(t->r, i + 1, r);
  73. build(t->l, l, i - 1);
  74. return;
  75. }
  76. }
  77. for(int i = l; i <= r; i++) {
  78. if (str[i] == ' ') continue;
  79. if (str[i] == '*') {
  80. t->r = &t[gg++];
  81. t->l = &t[gg++];
  82. t->number = false;
  83. t->value = 2;
  84. build(t->r, i + 1, r);
  85. build(t->l, l, i - 1);
  86. return;
  87. }
  88. if (str[i] == '/') {
  89. t->r = &t[gg++];
  90. t->l = &t[gg++];
  91. t->number = false;
  92. t->value = 3;
  93. build(t->r, i + 1, r);
  94. build(t->l, l, i - 1);
  95. return;
  96. }
  97. }
  98. }
  99.  
  100. void lpk(tree v) {
  101. if (v->l) lpk(v->l);
  102. if (v->r) lpk(v->r);
  103. if (v->number) cout << '(' << v->value << ')';
  104. else {
  105. if (v->value == 0) cout << "+";
  106. if (v->value == 1) cout << "-";
  107. if (v->value == 2) cout << "*";
  108. if (v->value == 3) cout << "/";
  109. }
  110.  
  111. }
  112.  
  113. int lkp(tree v) {
  114. int ans = 0, l = 0, r = 0;
  115. if (v->l) l = lkp(v->l);
  116. if (v->number) cout << v->value << ' ';
  117. else {
  118. if (v->value == 0) cout << "+ ";
  119. if (v->value == 1) cout << "- ";
  120. if (v->value == 2) cout << "* ";
  121. if (v->value == 3) cout << "/ ";
  122. }
  123. if (v->r) r = lkp(v->r);
  124. ///
  125. if (v->number) ans = v->value;
  126. else {
  127. if (v->value == 0) {
  128. ans = l + r;
  129. }
  130. if (v->value == 1){
  131. ans = l - r;
  132. }
  133. if (v->value == 2) {
  134. ans = l * r;
  135. }
  136. if (v->value == 3) {
  137. ans = l / r;
  138. }
  139. }
  140. return ans;
  141. }
  142.  
  143. char c[1000];
  144.  
  145. int main() {
  146. gets(c);
  147. str = c;
  148. tree root = &t[gg++];
  149. build(root, 0, str.size() - 1);
  150. lpk(root); cout << endl;
  151. printf("= %d\n", lkp(root));
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement