二进制表达式树C++

Question

我有一点问题。我试图给二叉树添加一个数学表达式，但我无法理解该算法。那就是：

If the current token is a '(': 
Add a new node as the left child of the current node, and 
descend to the left child. 
If the current token is in the list ['+','-','/','*']: 
Set the root value of the current node to the operator represented by the current token. 
Add a new node as the right child of the current node and descend to the right child. 
If the current token is a number: 
Set the root value of the current node to the number and return to the parent. 
If the current token is a ')': 
    go to the parent of the current node. 

和我迄今所取得的代码：

template<class T> 
void Tree<T>::Expr(Node<T> *node, char expr[], int &i) 
{ 
    i++; 
    T x = expr[i]; 
    if(x == '(') 
     { 
      node = node->Left; 

      node = new Node<T>; 
      node->Left = NULL; 
      node->Right = NULL; 
      Expr(node, expr, i); 
     } 
    if(x == '+' || x == '-' || x == '*' || x == '/') 
     { 
      node->data = x; 
      node = node->Right; 
      node = new Node<T>; 
      node->Left = NULL; 
      node->Right = NULL; 
      Expr(node, expr, i); 
     } 
    if(x >= '0' && x <= '9') 
     { 
      node->data = x; 
      return; 
     } 
    if(x == ')') return; 
} 

我知道这是一个很大的混乱，但我不能认识到如何实现它。有人可以向我解释算法或给我一个C++代码或更好解释算法的源代码吗？

P.S.下面是我写的新代码，但它仅适用于这样的表达式：（5 + 2）

template<class T> 
void Tree<T>::Expr(Node<T> *&node, char expr[], int &i) 
{ 
    i++; 
    if(i >= strlen(expr)) return; 
    char x = expr[i]; 
    node = new Node<T>; 
    node->Left = NULL; 
    node->Right = NULL; 
    if(x == '(') 
     { 
      Expr(node->Left, expr, i); 
      i++; 
      x = expr[i]; 
     } 
    if(x >= '0' && x <= '9') 
     { 
      node->data = x; 
      return; 
     } 
    if(x == '+' || x == '-' || x == '*' || x == '/') 
     { 
      node->data = x; 
      Expr(node->Right, expr, i); 
     } 
    if(x == ')') return; 
} 

Answer 1

下面是一个例子，我很久以前做了学习的目的：

#include <iostream> 
#include <list> 
#include <cassert> 
#include <stdexcept> 

/// \todo Because I'm short of time, there is no smart pointers or 
/// even destructors (w/ delete) :) -- THIS IS FAR FROM PRODUCTION CODE, 
/// but it is minimalistic to realize the idea... 

/** 
* \brief Expression abstract base class 
* 
* ... has only evaluate function. 
*/ 
struct expression 
{ 
    virtual ~expression() {}; 
    virtual int operator()() const = 0; 
}; 

struct number_token : public expression 
{ 
    int value_; 
    number_token(const int value = 0) : value_(value) {} 
    int operator()() const { 
     return value_; 
    } 
}; 

struct binary_predicate : public expression 
{ 
    expression* left_; 
    expression* right_; 

    binary_predicate(expression* const left = 0, expression* const right = 0) 
    : left_(left), right_(right) 
    {} 
}; 

struct plus : public binary_predicate 
{ 
    plus(expression* const left, expression* const right) 
    : binary_predicate(left, right) 
    {} 

    int operator()() const { 
     return (*left_)() + (*right_)(); 
    } 
}; 

struct minus : public binary_predicate 
{ 
    minus(expression* const left, expression* const right) 
    : binary_predicate(left, right) 
    {} 

    int operator()() const { 
     return (*left_)() - (*right_)(); 
    } 
}; 

struct mul : public binary_predicate 
{ 
    mul(expression* const left, expression* const right) 
    : binary_predicate(left, right) 
    {} 

    int operator()() const { 
     return (*left_)() * (*right_)(); 
    } 
}; 

struct div : public binary_predicate 
{ 
    div(expression* const left, expression* const right) 
    : binary_predicate(left, right) 
    {} 

    int operator()() const { 
     return (*left_)()/(*right_)(); 
    } 
}; 

class evaluator 
{ 
public: 
    const expression* parse(const char*);     ///< Parse an expression 

private: 
    expression* parse_number(const char*&);     ///< Parse numeric constants 
    expression* parse_atom(const char*&);     ///< Parse nested expression 
    expression* parse_summands(const char*&);    ///< Parse '+' and '-' operations 
    expression* parse_factors(const char*&);    ///< Parse '*' and '/' operations 
}; 

expression* evaluator::parse_number(const char*& s) 
{ 
    assert("Sanity check" && s && std::isdigit(*s)); 
    number_token* nt = new number_token(0); 
    // Convert number... 
    while (*s && std::isdigit(*s)) 
    { 
     nt->value_ = nt->value_ * 10 + *s++ - '0'; 
    } 
    return nt; 
} 

expression* evaluator::parse_atom(const char*& s) 
{ 
    assert("Sanity check" && s); 
    if (*s == 0) 
    { 
     throw std::runtime_error("Atom parse error: unexpected EOS"); 
    } 
    else if (*s == '(') 
    { 
     s++; 
     expression* atom = parse_summands(s); 
     if (*s == ')') 
     { 
      s++; 
      return atom; 
     } 
     throw std::runtime_error("Atom parse error: unbalanced brackets"); 

    } 
    else if (std::isdigit(*s)) 
    { 
     expression* atom = parse_number(s); 
     return atom; 
    } 
    throw std::runtime_error("Atom parse error: unexpected char"); 
} 

expression* evaluator::parse_factors(const char*& s) 
{ 
    assert("Sanity check" && s); 
    expression* left = parse_atom(s); 
    while (*s) 
    { 
     if (*s == '*') 
     { 
      s++; 
      expression* right = parse_atom(s); 
      left = new mul(left, right); 
      continue; 
     } 
     else if (*s == '/') 
     { 
      s++; 
      expression* right = parse_atom(s); 
      left = new div(left, right); 
      continue; 
     } 
     return left; 
    } 
    return left; 
} 

expression* evaluator::parse_summands(const char*& s) 
{ 
    assert("Sanity check" && s); 
    expression* left = parse_factors(s); 
    while (*s) 
    { 
     if (*s == '+') 
     { 
      s++; 
      expression* right = parse_factors(s); 
      left = new plus(left, right); 
      continue; 
     } 
     else if (*s == '-') 
     { 
      s++; 
      expression* right = parse_factors(s); 
      left = new minus(left, right); 
      continue; 
     } 
     return left; 
    } 
    return left; 
} 

const expression* evaluator::parse(const char* s) 
{ 
    return parse_summands(s); 
} 


int evaluate(const char* const e) 
{ 
    evaluator ev; 
    const expression* const ex = ev.parse(e); 
    assert("Sanity check" && ex); 
    return (*ex)(); 
} 

// s= evaluate(“(4+3)*2/5”); 
// s= evaluate(“((12+9)/2)*5”); 
int main() 
{ 
    { 
     int a = evaluate("(4+3)*2/5"); 
     assert("Unexpected result" && a == 2); 
     std::cout << "\"(4+3)*2/5\" = " << a << std::endl; 
    } 
    { 
     int a = evaluate("((12+9)/2)*5"); 
     assert("Unexpected result" && a == 50); 
     std::cout << "\"((12+9)/2)*5\" = " << a << std::endl; 
    } 
    return 0; 
}