class Node {

public:

   virtual int Compute() = 0;

   inline void SetLeft(Node* left) {

      left_ = left;

   }

   inline void SetRight(Node* right) {

      right_ = right;

   }

protected:

   Node* left_ = nullptr;

   Node* right_ = nullptr;

};

class SumNode : public Node {

public:

   inline int Compute() override {

      return left_->Compute() + right_->Compute();

   }

};

class SubNode : public Node {

public:

   inline int Compute() override {

      return left_->Compute() - right_->Compute();

   }

};

class MulNode : public Node {

public:

   inline int Compute() override {

      return left_->Compute() * right_->Compute();

   }

};

class NumNode : public Node {

public:

   NumNode(int num) : num_(num) {}

   inline int Compute() override {

      return num_;

   }

private:

   int num_;

};

class Solution {

public:

   vector<int> diffWaysToCompute(string expression) {



      vector<Node*> nodes;



// parse the expression

      for (int i = 0; i < expression.size(); ++i) {



         switch (expression[i]) {

         case '+':

            nodes.emplace_back(new SumNode());

            break;

         case '-':

            nodes.emplace_back(new SubNode());

            break;

         case '*':

            nodes.emplace_back(new MulNode());

            break;

         default:

            int num = 0;

            while (expression[i] >= '0' && expression[i] <= '9') {

               num = num * 10 + expression[i] - '0';

               ++i;

            }

            --i;

            nodes.emplace_back(new NumNode(num));

            break;

         }

      }



      vector<Node*> trees = GenerateAllTrees(nodes, 0, nodes.size() - 1);



      for (Node* node : nodes) {

         delete node;

      }



      vector<int> results;

      for (Node* tree : trees) {

         results.emplace_back(tree->Compute());

         delete tree;

      }

      return results;



   }



   vector<Node*> GenerateAllTrees(const vector<Node*> nodes, int beg, int end) {



      if (beg == end) {

         return {new NumNode(nodes[beg]->Compute())};

      }



      vector<Node*> results;



      for (int i = beg; i <= end; i++) {



// assuming the expression is well formed, operators will be in odd positions

         if ((i & 1) == 0) continue;



         vector<Node*> left_trees = GenerateAllTrees(nodes, beg, i - 1);

         vector<Node*> right_trees = GenerateAllTrees(nodes, i + 1, end);



         for (Node* left : left_trees) {

            for (Node* right : right_trees) {

               nodes[i]->SetLeft(left);

               nodes[i]->SetRight(right);

               Node* result = new NumNode(nodes[i]->Compute());

               results.emplace_back(result);

            }

         }

         for (Node* t : left_trees) {

            delete t;

         }

         for (Node* t : right_trees) {

            delete t;



         }



         return results;

      }