Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct node{
- bool number;
- int value;
- node *l, *r;
- ///0 +
- ///1 -
- ///2 *
- ///3 /
- };
- node t[10000];
- int gg = 0;
- #define tree node *
- string str;
- bool check(int l, int r) {
- if (l > r) return false;
- while(l <= r) {
- if (str[l] == ' ') {
- l++;
- continue;
- }
- if (str[l] < '0' || str[l] > '9') return false;
- l++;
- }
- return true;
- }
- int get_number(int l, int r) {
- if (l > r) return 0;
- int ans = 0, j = 1;
- while(l <= r) {
- if (str[r] == ' ') {
- r--;
- continue;
- }
- ans += (str[r] - '0') * j;
- j *= 10;
- r--;
- }
- return ans;
- }
- void build(tree t, int l , int r) {
- //cout << l << ' ' << r << endl;
- if (check(l, r)) {
- t->number = true;
- t->value = get_number(l, r);
- t->l = nullptr;
- t->r = nullptr;
- return;
- }
- for(int i = l; i <= r; i++) {
- if (str[i] == ' ') continue;
- if (str[i] == '+') {
- t->r = &t[gg++];
- t->l = &t[gg++];
- t->number = false;
- t->value = 0;
- build(t->r, i + 1, r);
- build(t->l, l, i - 1);
- return;
- }
- if (str[i] == '-') {
- t->r = &t[gg++];
- t->l = &t[gg++];
- t->number = false;
- t->value = 1;
- build(t->r, i + 1, r);
- build(t->l, l, i - 1);
- return;
- }
- }
- for(int i = l; i <= r; i++) {
- if (str[i] == ' ') continue;
- if (str[i] == '*') {
- t->r = &t[gg++];
- t->l = &t[gg++];
- t->number = false;
- t->value = 2;
- build(t->r, i + 1, r);
- build(t->l, l, i - 1);
- return;
- }
- if (str[i] == '/') {
- t->r = &t[gg++];
- t->l = &t[gg++];
- t->number = false;
- t->value = 3;
- build(t->r, i + 1, r);
- build(t->l, l, i - 1);
- return;
- }
- }
- }
- void lpk(tree v) {
- if (v->l) lpk(v->l);
- if (v->r) lpk(v->r);
- if (v->number) cout << '(' << v->value << ')';
- else {
- if (v->value == 0) cout << "+";
- if (v->value == 1) cout << "-";
- if (v->value == 2) cout << "*";
- if (v->value == 3) cout << "/";
- }
- }
- int lkp(tree v) {
- int ans = 0, l = 0, r = 0;
- if (v->l) l = lkp(v->l);
- if (v->number) cout << v->value << ' ';
- else {
- if (v->value == 0) cout << "+ ";
- if (v->value == 1) cout << "- ";
- if (v->value == 2) cout << "* ";
- if (v->value == 3) cout << "/ ";
- }
- if (v->r) r = lkp(v->r);
- ///
- if (v->number) ans = v->value;
- else {
- if (v->value == 0) {
- ans = l + r;
- }
- if (v->value == 1){
- ans = l - r;
- }
- if (v->value == 2) {
- ans = l * r;
- }
- if (v->value == 3) {
- ans = l / r;
- }
- }
- return ans;
- }
- char c[1000];
- int main() {
- gets(c);
- str = c;
- tree root = &t[gg++];
- build(root, 0, str.size() - 1);
- lpk(root); cout << endl;
- printf("= %d\n", lkp(root));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement