8ms C++ solution using OOP, Binary Expression Trees, and Recursion with Dynamic Programming


  • 0
    S
    static const char ADD = '+';
    static const char SUB = '-';
    static const char MUL = '*';
    
    class ExprNode;
    using ExprNodePtr = shared_ptr<ExprNode>;
    
    // abstract base class of a node in an expression tree
    class ExprNode
    {
    protected:
    
        ExprNodePtr _left;
        ExprNodePtr _right;
    
    public:
    
        ExprNode()
            : _left(nullptr)
            , _right(nullptr)
        {
        }
        virtual ~ExprNode() {}
    
        // evaluate this expression node, treating this node as a root of an expression tree
        virtual int eval() const = 0;
    
        // represent an expression tree rooted at this node, with proper parentheses
        virtual string to_string() const = 0;
    
    };
    
    
    // all leaves in an expression tree have this type
    class NumNode : public ExprNode
    {
    protected:
    
        int _value;
    
    public:
    
        NumNode(int v)
            : ExprNode()
            , _value(v)
        {
            _left = _right = nullptr;
        }
    
        inline int value() const { return _value; }
    
        /*override*/
        virtual int eval() const
        {
            return value();
        }
    
        /*override*/
        virtual string to_string() const
        {
            string repr = ::to_string(value());
            if (value() >= 0)
            {
                return repr;
            }
            else
            {
                repr = "(" + repr + ")";
                return repr;
            }
        }
    
    };
    
    
    // all non-leaf nodes in an expression tree are op nodes;
    // each op node MUST have left and right child nodes BOTH when evaluated
    class OpNode : public ExprNode
    {
    protected:
    
        char _op;
    
    public:
    
        OpNode(char op, ExprNodePtr left = nullptr, ExprNodePtr right = nullptr)
            : _op(op)
        {
            switch (op)
            {
            case ADD:
            case SUB:
            case MUL:
                break;
            default:
                throw invalid_argument("unknown op char!");
            }
    
            _left = left;
            _right = right;
        }
    
        inline void set_left(ExprNodePtr left) { _left = left; }
        inline void set_right(ExprNodePtr right) { _right = right; }
    
        /*override*/
        virtual int eval() const
        {
            // an op node MUST have  left AND  right child nodes!
            assert(_left != nullptr && _right != nullptr);
    
            int left_value = _left->eval();
            int right_value = _right->eval();
    
            switch (_op)
            {
            case ADD:
                return left_value + right_value;
            case SUB:
                return left_value - right_value;
            case MUL:
                return left_value * right_value;
            default:
                assert(false);
                break;
            }
        }
    
        /*override*/
        virtual string to_string() const
        {
            // an op node MUST have  left AND  right child nodes!
            assert(_left != nullptr && _right != nullptr);
    
            string left_expr_str = _left->to_string();
            string right_expr_str = _right->to_string();
    
            ostringstream ss;
            ss << "(" << left_expr_str << " " << _op << " " << right_expr_str << ")";
    
            return ss.str();
        }
    
    };
    
    
    /**
    * As a sub-problem to `evaluations()`, given an arithmetic expression,
    * generate all possible expression trees.
    *
    * HINT: Each unique expression tree will be rooted at each operator in
    *       the input expression.
    */
    vector<ExprNodePtr> expression_trees(const string &expr);
    
    // helper functions to aid the overall solution:
    static vector<string> tokenize(const string &expr);
    // the dp cache maps the tuple (start,end) indices to all possible expression
    // trees involving tokens[start..end]
    using dp_cache = map<pair<int, int>, vector<ExprNodePtr>>;
    // the key helper for expression_trees(), working with a sub-array of tokens
    static vector<ExprNodePtr> _expression_trees(const vector<string> &tokens, int start, int end,
        dp_cache &cache);
    // end helper functions
    
    
    // the input is like: "a+b-c*d" where a,b,... are positive integers with +,-,* between them
    /*static*/ vector<string> tokenize(const string &expr)
    {
        vector<string> tokens;
    
        const char *tok = &expr[0];
        const char *p = tok;
        while (*p)
        {
            switch (*p)
            {
            case ADD:
            case SUB:
            case MUL:
                // push the previous term
                tokens.push_back(string(tok, p - tok));
                tok = p + 1;
                // then push the operator itself
                tokens.push_back(string(1, *p));
                break;
            default:
                break;
            }
            ++p;
        }
    
        // push the last term
        tokens.push_back(string(tok));
    
        return tokens;
    }
    
    /*static*/ vector<ExprNodePtr> _expression_trees(const vector<string> &tokens, int start, int end,
        dp_cache &cache)
    {
        assert(start >= 0 && start < (int)tokens.size());
        assert(end >= 0 && end < (int)tokens.size());
    
        if (cache.find({ start, end }) != cache.end())
        {
            // the expression trees generation for tokens[start..end] have already been done!
            return cache[{start, end}];
        }
    
        vector<ExprNodePtr> trees;
    
        // base case:
        assert(start <= end);
        if (start == end)
        {
            // must be a leaf node
            ExprNodePtr leaf(new NumNode(atoi(tokens[start].c_str())));
            trees.push_back(leaf);
        }
        // recursive:
        else
        {
            for (int i = start; i <= end; ++i)
            {
                if (tokens[i].size() == 1 && !isdigit(tokens[i][0]))   // detect an op token
                {
                    char op_char = tokens[i][0];
                    vector<ExprNodePtr> left_trees = _expression_trees(tokens, start, i - 1, cache);
                    vector<ExprNodePtr> right_trees = _expression_trees(tokens, i + 1, end, cache);
                    // pair each left subtree with each right subtree
                    for (ExprNodePtr left_tree : left_trees)
                    {
                        for (ExprNodePtr right_tree : right_trees)
                        {
                            ExprNodePtr root(new OpNode(op_char,
                                left_tree, right_tree));
                            trees.push_back(root);
                        }
                    }
                }
            }
        }
    
        cache[{start, end}] = trees;
        return trees;
    }
    
    vector<ExprNodePtr> expression_trees(const string &expr)
    {
        vector<string> tokens = tokenize(expr);
        dp_cache cache;
        return _expression_trees(tokens, 0, tokens.size() - 1, cache);
    }
    
    vector<int> evaluations(const string &expr)
    {
        vector<int> result;
    
        vector<ExprNodePtr> all_trees = expression_trees(expr);
        for (const ExprNodePtr &tree : all_trees)
        {
            int eval = tree->eval();
            result.push_back(eval);
        }
    
        return result;
    }
    
    
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            return evaluations(input);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.