Verbose C++ solution, but with SAX style abstraction and unit tests


  • 0
    D

    This abstraction helps me think about the problem more clearly and makes it easier to unit test.

    #include <vector>
    #include <sstream>
    #include <cctype>
    #include <iostream>
    #include <cassert>
    #include <stack>
    using namespace std;
    
    class Node {
    public:
        Node(int k): k(k){}
        int k;
        string body;
    
        string expand() {
            string ret;
            for (int i = 0; i < k; i++) {
                ret += body;
            }
            return ret;
        }
    };
    class Solution {
    public:
        void handleStart(int k) {
            Node n(k);
            stack_.push(n);
        }
        void handleEnd() {
            Node cur = stack_.top();
            stack_.pop();
            if (!stack_.empty()) {
                Node& parent = stack_.top();
                parent.body += cur.expand();
            } else {
                result += cur.expand();
            }
        }
        void handleChar(char c) {
            if (stack_.empty()) {
                result +=c ;
            } else {
                Node& top = stack_.top();
                top.body += c;
            }
        }
    
        void handleChars(string chars) {
            Node& top = stack_.top();
            top.body += chars;
        }
    
        string decodeString(string s) {
            int k = 0;
            for (int i = 0; i < s.size(); i++) {
                if (isdigit(s[i])) {
                    k = k*10 + s[i] - '0';
                } else if (s[i] == '[') {
                    handleStart(k);
                    k = 0;
                } else if (s[i] == ']') {
                    handleEnd();
                } else {
                    handleChar(s[i]);
                }
            }
            return result;
        }
        string result;
    private:
        stack<Node> stack_;
    };
    
    TEST(Handlers, Smoke) {
        Solution s;
        s.handleStart(3);
        s.handleChars("ab");
        s.handleEnd();
        EXPECT_EQ("ababab", s.result);
    }
    TEST(Handlers, Nested) {
        Solution s;
        s.handleStart(2);
        s.handleStart(2);
        s.handleChars("ab");
        s.handleEnd();
        s.handleEnd();
        EXPECT_EQ("abababab", s.result);
    }
    TEST(Handlers, Peers) {
        Solution s;
        s.handleStart(2);
        s.handleChars("ab");
        s.handleEnd();
        s.handleStart(3);
        s.handleChars("c");
        s.handleEnd();
        EXPECT_EQ("ababccc", s.result);
    }
    TEST(Handlers, NestedPeers) {
        Solution s;
        s.handleStart(2);
            s.handleChars("ab");
            s.handleStart(2);
            s.handleChars("c");
            s.handleEnd();
        s.handleEnd();
        EXPECT_EQ("abccabcc", s.result);
    }
    TEST(Decode, Smoke) {
        Solution s;
        EXPECT_EQ("ababab", s.decodeString("3[ab]"));
    }
    
    TEST(Decode, Peers) {
        Solution s;
        EXPECT_EQ("ababab", s.decodeString("1[ab]2[ab]"));
    }
    
    }
    TEST(Decode, Peers2) {
        Solution s;
        EXPECT_EQ("", s.decodeString("3[cd]ef"));
    }
    
    TEST(Decode, Nest) {
        Solution s;
        EXPECT_EQ("abababab", s.decodeString("2[2[ab]]"));
    }
    TEST(Decode, NestAndPeer) {
        Solution s;
        EXPECT_EQ("abceabce", s.decodeString("2[1[ab]1[ce]]"));
    }
    TEST(Decode, Empty) {
        Solution s;
        EXPECT_EQ("", s.decodeString(""));
    }
    TEST(Decode, MixPeer) {
        Solution s;
        EXPECT_EQ("abcbcabcbcabcbc", s.decodeString("3[a2[bc]]"));
    }
    TEST(Decode, Peer2) {
        Solution s;
        EXPECT_EQ("", s.decodeString("3[cd]ef"));
    }
    

Log in to reply
 

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