// buspuzzle.h

#ifndef BUSPUZZLE_H
#define BUSPUZZLE_H

#include <string>
#include <set>

typedef uint8_t byte;

std::string busPuzzleSolve(std::string input);

class BinTree
{
  private:
    struct BinTreeException {};
    struct BinTreeIncorrectSeed: BinTreeException {};
    struct BinTreeLastTree: BinTreeException {};
    struct BinTreeDivisionError: BinTreeException {};

    enum Operation
    {
      CONCAT, ADD, SUB, MUL, DIV, NUMBER
    } type;

    static const char operationSymbol[];

    byte* digit;

    byte leftSize;

    byte size;
    BinTree *left, *right;

    void buildNext();
    void generateSubTrees();
    std::string filterSolutions(std::set<std::string> solutions);

  public:
    BinTree(const char* seed);
    ~BinTree();

    int compute();
    Operation getType();
    std::string toString(bool parentheses = true);

    std::string solve();
};

#endif // BUSPUZZLE_H

//-------------------------------------------------------------------------------------//

// buspuzzle.cpp

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <cstring>

#include "buspuzzle.h"

std::string busPuzzleSolve(std::string input)
{
  return BinTree(input.c_str()).solve();
}

const char BinTree::operationSymbol[] = {' ', '+', '-', '*', '/'};

BinTree::BinTree(const char* seed)
{
  size = strlen(seed);

  leftSize = 1;

  if (size == 1)
    type = NUMBER;
  else
    type = CONCAT;

  digit = new byte[size];
  for (int i = 0; i < size; i++)
  {
    if (!isdigit(seed[i]))
      throw BinTreeIncorrectSeed();

    digit[i] = seed[i] - '0';
  }

  left = right = NULL;

  if (type != NUMBER)
  {
    generateSubTrees();
  }
}

BinTree::~BinTree()
{
  delete left;
  delete right;
  delete[] digit;
}

void BinTree::buildNext()
{
  if (type == NUMBER)
      throw BinTreeLastTree();
  try
  {
    left->buildNext();
  }
  catch (BinTreeLastTree)
  {
    try
    {
      right->buildNext();
    }
    catch (BinTreeLastTree)
    {
      bool isLast = false;

      leftSize++;
      if (leftSize == size)
      {
        leftSize = 1;

        type = (Operation)(type + 1);
        if (type == NUMBER)
        {
          type = CONCAT;
          isLast = true;
        }
      }

      delete left;
      delete right;
      generateSubTrees();

      if (isLast)
        throw BinTreeLastTree();
    }
  }
}

void BinTree::generateSubTrees()
{
  char *leftSeed = new char[leftSize + 1];
  char *rightSeed = new char[size - leftSize + 1];

  for (int i = 0; i < leftSize; i++)
  {
    leftSeed[i] = digit[i] + '0';
  }
  leftSeed[leftSize] = '\0';

  for (int i = 0; i < size - leftSize; i++)
  {
    rightSeed[i] = digit[i+leftSize] + '0';
  }
  rightSeed[size-leftSize] = '\0';

  left = new BinTree(leftSeed);
  right = new BinTree(rightSeed);

  delete[] leftSeed;
  delete[] rightSeed;
}

int BinTree::compute()
{
  switch (type)
  {
    case CONCAT:
      if ((left->getType() == NUMBER || left->getType() == CONCAT) &&
          left->compute() != 0 && right->getType() == NUMBER)
        return left->compute()*10 + right->compute();
      else
        break;

    case ADD:
      return left->compute() + right->compute();

    case SUB:
      return left->compute() - right->compute();

    case MUL:
      return left->compute() * right->compute();

    case DIV:
      {
        int l = left->compute(), r = right->compute();
        if ((r == 0) || (l%r != 0))
          throw BinTreeDivisionError();

        return l/r;
      }

    case NUMBER:
      return digit[0];

    default:
      ;
  }
  throw BinTreeException();
}

BinTree::Operation BinTree::getType()
{
  return type;
}

std::string BinTree::toString(bool parentheses)
{
  switch (type)
  {
    case CONCAT:
      return left->toString() + right->toString();

    case ADD:
      {
        std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)),
                    rightStr = right->toString(!(right->getType() == ADD || right->getType() == SUB));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":"");
      }

    case SUB:
      {
        std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + right->toString() + (parentheses?")":"");
      }

    case MUL:
      {
        std::string leftStr = left->toString(!(left->getType() == MUL || left->getType() == DIV)),
                    rightStr = right->toString(!(right->getType() == MUL || right->getType() == DIV));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":"");
      }

    case DIV:
      return (parentheses?"(":"") + left->toString() + operationSymbol[type] + right->toString() + (parentheses?")":"");

    case NUMBER:
      {
        char str[2] = {(char)(digit[0]+'0'), '\0'};
        return str;
      }

    default:
      ;
  }
  throw BinTreeException();
}

std::string BinTree::solve()
{
  std::set<std::string> solutions;

  try
  {
    while (true)
    {
      buildNext();

      int result = 0;
      try
      {
        result = compute();
      }
      catch (...)
      {
        //
      }

      if (result == 100)
        solutions.insert(toString(false));
    }
  }
  catch (BinTreeLastTree)
  {
    //
  }

  return filterSolutions(solutions);
}

std::string BinTree::filterSolutions(std::set<std::string> solutions)
{
  std::string filtered = "";

  for (std::set<std::string>::iterator i = solutions.begin(); i != solutions.end(); ++i)
  {
    filtered += *i + "\n";
  }
  return filtered;
}