Saturday, November 5, 2016

LeetCode OJ - Decode String

Problem:

Please find the problem here.

Solution: 

A relatively straightforward (but complex) implementation based on top-down recursive parsing and tree walking interpretation.

Care is taken to ensure shorter code (e.g. no class for scanner/token/parser), things are done in a relatively messy yet short way.

Looking in retrospect, this is a really good problem for interviewing a compiler job.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/decode-string/

#include "LEET_DECODE_STRING.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_DECODE_STRING
{
    class Solution
    {
    private:
        // position pointing at the next unscaned character
        int p;
        // 1: string
        // 2: number
        // 3: [
        // 4: ]
        // 5: eof
        int token_type;
        int n;
        string t;

        void scan(string& text)
        {
            if (p == text.length())
            {
                token_type = 5;
            }
            else if (text[p] == '[')
            {
                token_type = 3;
                p++;
            }
            else if (text[p] == ']')
            {
                token_type = 4;
                p++;
            }
            else if ('0' <= text[p] && text[p] <= '9')
            {
                this->n = 0;
                token_type = 2;
                while (p != text.length() && '0' <= text[p] && text[p] <= '9')
                {
                    n *= 10;
                    n += (text[p] - '0');
                    p++;
                }
            }
            else
            {
                this->token_type = 1;
                this->t = "";
                while (p != text.length() && text[p] != '[' && text[p] != ']' && !('0' <= text[p] && text[p] <= '9'))
                {
                    t += text[p];
                    p++;
                }
            }
        }

        class command
        {
        public:
            virtual void execute(ostringstream& sout) = 0;
        };
        class string_command : public command
        {
        public:
            string_command(string s) { this->s = s; }
            string s;
            virtual void execute(ostringstream& sout)
            {
                sout << s;
            }
        };
        class repeat_command : public command
        {
        public:
            repeat_command(int times, vector<command*> body)
            {
                this->times = times;
                this->body = body;
            }
            int times;
            vector<command*> body;

            virtual void execute(ostringstream& sout)
            {
                for (int i = 0; i < this->times; i++)
                {
                    for (auto&& command : this->body)
                    {
                        command->execute(sout);
                    }
                }
            }
        };
    public:
        string decodeString(string s)
        {
            this->p = 0;
            this->scan(s);
            vector<command*> commands = parseInput(s);
            ostringstream sout;
            for (auto&& command : commands)
            {
                command->execute(sout);
            }
            return sout.str();
        }

        vector<command*> parseInput(string& s)
        {
            vector<command*> result;
            while (true)
            {
                if (this->token_type == 5 || this->token_type == 4)
                {
                    return result;
                }
                else if (this->token_type == 1)
                {
                    result.push_back(new string_command(t));
                    this->scan(s);
                }
                else if (this->token_type == 2)
                {
                    int r = n;
                    this->scan(s);
                    if (this->token_type == 3)
                    {
                        this->scan(s);
                        vector<command*> recursive_result = parseInput(s);
                        if (this->token_type == 4)
                        {
                            this->scan(s);
                            result.push_back(new repeat_command(r, recursive_result));
                        }
                        else
                        {
                            throw 2;
                        }
                    }
                    else
                    {
                        throw 1;
                    }
                }
            }

        }

    };
};

using namespace _LEET_DECODE_STRING;

int LEET_DECODE_STRING()
{
    Solution solution;
    cout << solution.decodeString("3[a]2[bc]") << endl;
    cout << solution.decodeString("3[a2[c]]") << endl;
    cout << solution.decodeString("2[abc]3[cd]ef") << endl;
    return 0;
}

No comments :

Post a Comment