Design an Expression Tree With Evaluate Function
给一个postfix的表达式数, 让设计一个Node, 里面有evaluate方法, 可以算出答案.
这个题是偏设计, 所以一般不用全局的stack算, 上来给了个node的抽象类, 然后通过观察可以看到有数字+加减乘除几种node组成, 分辨写出这几个node. 然后输入的string是postfix, 所以只需要从后往前一个个扫描即可建树.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
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)); } } }; |