Design an Expression Tree With Evaluate Function

给一个postfix的表达式数, 让设计一个Node, 里面有evaluate方法, 可以算出答案.

这个题是偏设计, 所以一般不用全局的stack算, 上来给了个node的抽象类, 然后通过观察可以看到有数字+加减乘除几种node组成, 分辨写出这几个node. 然后输入的string是postfix, 所以只需要从后往前一个个扫描即可建树.

class Node {
public:
    Node(Node* l, Node* r) : left(l), right(r){} 
    virtual ~Node () {};
    virtual int evaluate() const = 0;
protected:
    Node* left;
    Node* right;
};

class VNode : public Node {
    public:
    VNode(int value) : Node(nullptr, nullptr), val(value){}
    int evaluate() const{
        return val;
    }
    protected:
    int val;
};

class Plus : public Node {
    public:
    Plus(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return left->evaluate() + right->evaluate();
    }
};

class Minus : public Node {
    public:
    Minus(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return right->evaluate() - left->evaluate();
    }
};
class Multiply : public Node {
    public:
    Multiply(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return left->evaluate() * right->evaluate();
    }
};
class Divide : public Node {
    public:
    Divide(Node* l, Node* r) : Node(l, r){}
    protected:
    int evaluate() const{
        return right->evaluate() / left->evaluate();
    }
};
class TreeBuilder {
public:
    Node* buildTree(vector<string>& postfix) {
        if(postfix.size() == 0)
            return nullptr;
        string s  = postfix.back();
        postfix.pop_back();
        if(!isdigit(s[0])){
            auto left = buildTree(postfix);
            auto right = buildTree(postfix);
            if(s == "+"){
                return new Plus(left, right);
            }else if(s == "-"){
                return new Minus(left, right);
            }else if (s == "*")
            {
                return new Multiply(left, right);
            }else
            {
                return new Divide(left, right);
            }
        }else{
            return new VNode(stoi(s));
        }
    }
};