Дерево разбора

#include <string>
#include <iostream>
#include <sstream>
#include <cassert>
 
enum Type{PLUS,MUL,VAL};
 
struct Node;
 
struct Node
{ 
   Type type;
   Node* left, *right;
   int data;
};
 
void recurs( std::string str, Node* node )
{
  
   int i, c; 
  
   std::cout << str << std::endl; 
   for( unsigned t = PLUS; t < VAL; ++t )
      for( i=0, c=0;i<str.size();++i )
      {
          if( '(' == str[i] )
            ++c;
          else if( ')' == str[i] )
            --c;
          else if( (t == PLUS ? '+' : '*') == str[i] && !c )
          {
            node->left = new Node;
            node->right = new Node; 
            node->type = static_cast<Type>( t ); 
            std::cout << ( node->type == PLUS ? "+" : "*" ) << std::endl; 
            recurs( str.substr( 0, i ), node->left );
            recurs( str.substr( i+1, str.size() - i ), node->right ); 
            return; 
          }        
      } 
     
   if( str[0] == '(' && str[str.size()-1] == ')' )
   { 
      recurs( str.substr( 1, str.size() - 2 ), node ); 
      return; 
   } 
     
   node->type = VAL;
   std::stringstream istr( std::stringstream::in | std::stringstream::out );
   istr << str;
   istr >> node->data; 
}
 
int recurs( Node* node )
{
  std::cout << "<<" << std::endl;
  int val = 0; 
  switch( node->type )
  {
    case PLUS:  
      val = recurs( node->left ) + recurs( node->right );
      break; 
    case MUL:
      val = recurs( node->left ) * recurs( node->right );  
      break; 
    case VAL:
      val = node->data;
      std::cout << "(" << val << ")" << std::endl;
      break; 
    default:
      assert( 0 );  
      return -1;  
  }   
  delete node; 
  return val; 
} 
 
int main()
{
   std::string str = "(((10+1)*(5+6*(3+1))+4*(3+1)))";
   Node* node = new Node;;
   recurs( str, node );
   std::cout << "result = " << recurs( node );  
}

struct Prior
{
    enum Priority {one=1, two=2, three=3};
};
 
class Token
{
public:
    Token(char c_='0', int t_=0, Prior::Priority pr_=Prior::one):
      c(c_), t(t_), pr(pr_)
    {
    }
    const char GetKind() const
    {
        return c;
    }
    const int GetNumb() const
    {
        return t;
    }
    const Prior::Priority GetPrior() const
    {
        return pr;
    }
private:
    int t;
    char c;
    Prior::Priority pr;
};
 
class Parser
{
public:
    Parser():sem_tree(Tree<Token>())
    {
    }
    void create_tree(std::string& str);
    Tree<Token> sem_tree;
private:
    bool lays_check(const std::string& str);
    template<class TernaryFunction>
    std::pair<std::string, std::string> create_tree_helper(std::string& str, TernaryFunction foo);
};
 
bool isNumeric(const std::string& some)
{
    int one=0;
    std::stringstream ss(some);
    ss >> one;
    std::stringstream ss2;
    ss2<<one;
    return (one && some.find_first_not_of(ss2.str()) == std::string::npos); 
}
 
std::string::iterator find_first_in_brakes_helper(std::string& some, const char first, const char second)
{
    std::string tmp;
    tmp+=first;
    tmp+=second;
    std::string::iterator iter;
    size_t idx=0;
    if(*some.begin() == '(' && *(some.begin()+1) == '(')
        idx=some.find_last_of(tmp);
    else
        idx=some.find_first_of(tmp);
    if(idx != std::string::npos)
    {
        iter=some.begin()+idx;
        some.erase(std::find(some.begin(), some.end(), '('));
        some.erase(std::find(some.begin(), some.end(), ')'));
        iter-=1;
        return iter;
    }
    return some.end();
}
 
std::pair<std::pair<std::string, std::string>, bool> find_first_in_brakes(std::string& some, const char first, const char second)
{
    if(isNumeric(some))
        return std::make_pair(std::make_pair(some, ""), true);
    std::string::iterator iter=find_first_in_brakes_helper(some, first, second);
    if(iter == some.end())
        return std::make_pair(std::make_pair("",""), false);
    std::string begin;
    begin.assign(some.begin(), ++iter);
    std::string end;
    end.assign(iter, some.end());
    return std::make_pair(std::make_pair(begin, end), true);
}
 
std::string::const_iterator find_first_without_brakes_helper(const std::string& some, const char first, const char second)
{
    std::stack<char> lays;
    for(std::string::const_iterator iter=some.begin(); iter != some.end(); ++iter)
    {
        if(*iter == '(')
            lays.push(*iter);
        else if(*iter == ')')
            lays.pop();
        if(lays.empty() && (*iter == first || *iter == second))
        {
            return iter;
        }
    }
    return some.end();
}
 
std::pair<std::pair<std::string,std::string>, bool> find_first_without_brakes(const std::string& some, const char first, const char second)
{
    if(isNumeric(some))
        return std::make_pair(std::make_pair(some, ""), true);
    std::string::const_iterator iter=find_first_without_brakes_helper(some, first, second);
    if(iter == some.end())
        return std::make_pair(std::make_pair("", ""), false);
    std::string res;
    res.assign(some.begin(), ++iter);
    std::string end;
    end.assign(iter, some.end());
    return std::make_pair(std::make_pair(res, end), true);
}
 
template<class TernaryFunction>
std::pair<std::string, std::string> Parser::create_tree_helper(std::string &str, TernaryFunction foo)
{
    const std::string opers="+-*/";
    bool state=false;
    std::string left;
    std::string right;
    for(std::string::const_iterator iter=opers.begin(); iter != opers.end(); iter+=2)
    {
    std::pair<std::pair<std::string, std::string>, bool> pair;
    pair=foo(str, *iter, *(iter+1));
    if(pair.second == true)
    {
        left=pair.first.first;
        right=pair.first.second;
        char c='\n';
        if(opers.find(left[left.size()-1]) != std::string::npos && !left.empty())
        {
            c=left[left.size()-1];
            left.resize(left.size()-1);
        }
        str.clear();
        std::cout<<left<<'\n'<<c<<'\n'<<right<<'\n';
        std::cout<<'\n';
        if(isNumeric(left))
            left.clear();
        if(isNumeric(right))
            right.clear();
        state=true;
        break;
    }
    else
        continue;
    }
    return std::make_pair(left, right);
}
 
void Parser::create_tree(std::string& str)
{
    if(!lays_check(str))
        throw std::runtime_error("Expression is incorrect");
    std::string left;
    std::string right;
    std::pair<std::string, std::string> left_right=create_tree_helper(str, find_first_without_brakes);
    if(left_right.first.empty() && left_right.second.empty())
        left_right=create_tree_helper(str, find_first_in_brakes);
    left=left_right.first;
    right=left_right.second;
    if(!left.empty())
        create_tree(left);
    if(!right.empty())
        create_tree(right);
}
 
bool Parser::lays_check(const std::string& str)
{
    std::stack<char> stck;
    for(std::string::const_iterator iter=str.begin(); iter != str.end(); ++iter)
    {
        if(*iter == '(')
            stck.push(*iter);
        else if(*iter == ')')
            stck.pop();
    }
    return stck.empty();
}
 
int main()
{
    Parser one;
    one.create_tree(std::string("(10+1)*(5+6*(3+1))+4*(3+1)"));
    return 0;
}

struct Tree;
 
typedef boost::variant<
        boost::recursive_wrapper<Tree>
        , std::string
    > Tree_node;
 
struct Tree
    {
    std::string _operator;
    std::vector<Tree_node> children;
    };
 
BOOST_FUSION_ADAPT_STRUCT(
    Tree,
    (std::string,_operator)
    (std::vector<Tree_node>,children)
    )