2

我有一个小问题。我正在尝试向二叉树添加数学表达式，但我无法理解该算法。这里是：

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++ 代码或更好解释算法的源代码吗？

PS 这是我编写的新代码，但它仅适用于以下表达式：(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;
}
4

1 回答 1

9

这是我很久以前为学习目的而做的一个例子：

#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;
}
于 2013-07-23T11:51:08.817 回答