Advertisement
dan-masek

Untitled

Dec 7th, 2019
322
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.84 KB | None | 0 0
  1. #include <cctype>
  2. #include <iostream>
  3. #include <memory>
  4. #include <sstream>
  5. #include <vector>
  6.  
  7. class node
  8. {
  9. public:
  10.     virtual ~node() = default;
  11.     virtual void evaluate(std::ostream& output) const = 0;
  12. };
  13.  
  14. using node_ptr = std::unique_ptr<node>;
  15. using node_sequence = std::vector<node_ptr>;
  16.  
  17. class literal : public node
  18. {
  19. public:
  20.     explicit literal(char symbol) : symbol_(symbol) {}
  21.    
  22.     void evaluate(std::ostream& output) const override
  23.     {
  24.         output.put(symbol_);
  25.     }
  26.  
  27. private:
  28.     char symbol_;
  29. };
  30.  
  31. class repetition : public node
  32. {
  33. public:
  34.     explicit repetition(size_t count) : count_(count)
  35.     {
  36.         if (count < 1) {
  37.             throw std::runtime_error("Invalid repetition count");
  38.         }
  39.     }
  40.  
  41.     void evaluate(std::ostream& output) const override
  42.     {
  43.         for (size_t i(0); i < count_; ++i) {
  44.             for (auto const& child : children) {
  45.                 child->evaluate(output);
  46.             }
  47.         }
  48.     }
  49.  
  50.     node_sequence children;
  51. private:
  52.     size_t count_;
  53. };
  54.  
  55. size_t parse_count(std::istream& input)
  56. {
  57.     size_t count(0);
  58.  
  59.     while (input) {
  60.         int const next_symbol = input.peek();
  61.         if (std::isdigit(next_symbol)) {
  62.             count = count * 10 + (input.get() - '0');
  63.         } else {
  64.             break;
  65.         }
  66.     }
  67.  
  68.     return count;
  69. }
  70.  
  71. void parse_required_symbol(std::istream& input, char c)
  72. {
  73.     if (input.peek() == EOF) {
  74.         throw std::runtime_error("Unexpected end if input.");
  75.     }
  76.     if (input.get() != c) {
  77.         throw std::runtime_error("Unexpected input symbol.");
  78.     }
  79. }
  80.  
  81. void parse_sequence(std::istream& input, node_sequence& children);
  82.  
  83. std::unique_ptr<literal> parse_literal(std::istream& input)
  84. {
  85.     return std::make_unique<literal>(input.get());
  86. }
  87.  
  88. std::unique_ptr<repetition> parse_repetition(std::istream& input)
  89. {
  90.     // First the repetition count
  91.     size_t const count = parse_count(input);
  92.  
  93.     // Now we expect an opening paren
  94.     parse_required_symbol(input, '(');
  95.  
  96.     auto repeat_node = std::make_unique<repetition>(count);
  97.     parse_sequence(input, repeat_node->children);
  98.  
  99.     // Now we expect a closing paren
  100.     parse_required_symbol(input, ')');
  101.  
  102.     return repeat_node;
  103. }
  104.  
  105. void parse_sequence(std::istream& input, node_sequence& children)
  106. {
  107.     while (input) {
  108.         char const next_symbol = input.peek();
  109.         if (std::isalpha(next_symbol)) {
  110.             children.push_back(parse_literal(input));
  111.         } else if (std::isdigit(next_symbol) && (next_symbol != '0')) {
  112.             children.push_back(parse_repetition(input));
  113.         } else {
  114.             break;
  115.         }
  116.     }
  117. }
  118.  
  119. node_ptr parse_stream(std::istream& input)
  120. {
  121.     auto root_node = std::make_unique<repetition>(1);
  122.  
  123.     parse_sequence(input, root_node->children);
  124.  
  125.     if (input.peek() != EOF) {
  126.         std::string remainder(std::istreambuf_iterator<char>(input), {});
  127.         throw std::runtime_error("Incomplete parse (remainder='" + remainder + "').");
  128.     }
  129.  
  130.     return root_node;
  131. }
  132.  
  133. std::string decompress(std::string compressed)
  134. {
  135.     std::stringstream input(compressed);
  136.  
  137.     node_ptr ast = parse_stream(input);
  138.  
  139.     std::stringstream output;
  140.     ast->evaluate(output);
  141.  
  142.     return output.str();
  143. }
  144.  
  145. int main()
  146. {
  147.     std::vector<std::string> test_strings = {
  148.         "ABCD"
  149.         , "AB2(CD)"
  150.         , "2(AB3(CD))EF"
  151.         , "AB(CD"
  152.         , "AB2(CD"
  153.         , "AB2(CD))"
  154.     };
  155.  
  156.     for (auto const& test_string : test_strings) {
  157.         std::cout << "Input = '" << test_string << "'\n";
  158.         try {
  159.             auto const decompressed = decompress(test_string);
  160.             std::cout << "Output = '" << decompressed << "'\n";
  161.         } catch (std::runtime_error& e) {
  162.             std::cout << "Error: " << e.what() << '\n';
  163.         }
  164.     }
  165.  
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement