mickypinata

PROG-T1013: Expression

Sep 18th, 2021
822
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node {
  5.     char dat;
  6.     vector<node*> nxt;
  7.     node(char dat): dat(dat) {};
  8. };
  9.  
  10. int prior(char c){
  11.     if(c == '+'){
  12.         return 1;
  13.     } else if(c == '*'){
  14.         return 2;
  15.     } else if(c == '^'){
  16.         return 3;
  17.     }
  18.     return -1;
  19. }
  20.  
  21. node *fuse(node *f, node *op, node *s){
  22.     if(f -> dat == op -> dat){
  23.         f -> nxt.push_back(s);
  24.         return f;
  25.     }
  26.     op -> nxt.push_back(f);
  27.     op -> nxt.push_back(s);
  28.     return op;
  29. }
  30.  
  31. void inOrder(node *root){
  32.     if(root -> dat == '('){
  33.         cout << '(';
  34.         inOrder(root -> nxt[0]);
  35.         cout << ')';
  36.         return;
  37.     }
  38.     if(root -> nxt.empty()){
  39.         cout << root -> dat;
  40.         return;
  41.     }
  42.     for(int i = 0; i < (int)(root -> nxt.size()) - 1; ++i){
  43.         inOrder(root -> nxt[i]);
  44.         cout << root -> dat;
  45.     }
  46.     inOrder(root -> nxt.back());
  47. }
  48.  
  49. void query(node *root, int i, vector<int> &acc){
  50.     if(i == acc.size()){
  51.         inOrder(root);
  52.         return;
  53.     }
  54.     if(acc[i] > root -> nxt.size()){
  55.         if(acc[i] == 1){
  56.             cout << root -> dat;
  57.         } else {
  58.             cout << "null";
  59.         }
  60.         return;
  61.     }
  62.     query(root -> nxt[acc[i] - 1], i + 1, acc);
  63. }
  64.  
  65. int main(){
  66.  
  67.     string str;
  68.     cin >> str;
  69.     str = '(' + str + ')';
  70.     stack<node*> stk;
  71.     for(int i = 0; i < str.size(); ++i){
  72.         char c = str[i];
  73.         if(c == '('){
  74.             stk.push(new node('('));
  75.         } else if(c == ')'){
  76.             node *s, *op, *f;
  77.             while(!stk.empty()){
  78.                 s = stk.top();
  79.                 stk.pop();
  80.                 op = stk.top();
  81.                 stk.pop();
  82.                 if(op -> dat == '('){
  83.                     stk.push(new node('('));
  84.                     stk.top() -> nxt.push_back(s);
  85.                     break;
  86.                 }
  87.                 f = stk.top();
  88.                 stk.pop();
  89.                 stk.push(fuse(f, op, s));
  90.             }
  91.         } else if(prior(c) != -1){
  92.             node *s, *op, *f;
  93.             while(!stk.empty()){
  94.                 s = stk.top();
  95.                 stk.pop();
  96.                 op = stk.top();
  97.                 stk.pop();
  98.                 if(op -> dat == '(' || prior(op -> dat) < prior(c)){
  99.                     stk.push(op);
  100.                     stk.push(s);
  101.                     break;
  102.                 }
  103.                 f = stk.top();
  104.                 stk.pop();
  105.                 stk.push(fuse(f, op, s));
  106.             }
  107.             stk.push(new node(c));
  108.         } else {
  109.             stk.push(new node(c));
  110.         }
  111.     }
  112.     node *root = stk.top() -> nxt[0];
  113.     int Q;
  114.     scanf("%d", &Q);
  115.     while(Q--){
  116.         vector<int> acc;
  117.         while(true){
  118.             int x;
  119.             scanf("%d", &x);
  120.             if(x == 0){
  121.                 break;
  122.             }
  123.             acc.push_back(x);
  124.         }
  125.         for(int i = (int)acc.size() - 1; i >= 0; --i){
  126.             cout << "op(" << acc[i] << ',';
  127.         }
  128.         cout << 'p';
  129.         for(int i = 0; i < acc.size(); ++i){
  130.             cout << ')';
  131.         }
  132.         cout << '=';
  133.         query(root, 0, acc);
  134.         cout << '\n';
  135.     }
  136.  
  137.     return 0;
  138. }
  139.  
RAW Paste Data