current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

This is my second attempt (version 1) at writing a string formatting utility which uses parsing. This time I more explicitly designed it as a finite state machine. I have very little experience with writing FSMs. As before, I'm not 100% sure that this code does not contain any critical flaws. In addition to pointing out any such oversights, I would appreciate advice on how this could be modified to make it either faster or more readable.

#include <boost/lexical_cast.hpp>
#include <iostream>
#include <string>
#include <stdexcept>
#include <utility>
#include <cctype>

using std::to_string;

template <class T>
std::string to_string(T&& item)
{
    return boost::lexical_cast<std::string>(std::forward<T>(item));   
}

template <class... Args>
std::string format(const std::string& fmt, Args&&... args)
{
    std::string arg_strs[] = { to_string(std::forward<Args>(args))... };

    std::string output, index;
    output.reserve(fmt.length() * 2);

    enum { COPYING, OPEN_BRACE, READ_INDEX, CLOSE_BRACE } state = COPYING;

    for (const char c : fmt) 
    {
        switch (state)
        {
            case COPYING:
                if (c == '{') state = OPEN_BRACE;
                else if (c == '}') state = CLOSE_BRACE;
                else output += c;
                break;

            case OPEN_BRACE:
                if (isdigit(c)) {
                    index += c;
                    state = READ_INDEX;
                }
                else if (c == '{') {
                    output += '{';
                    state = COPYING;
                }
                else goto fail;
                break;

            case READ_INDEX:
                if (isdigit(c)) index += c;
                else if (c == '}') {
                    size_t i = std::stoi(index);
                    if (i >= sizeof...(args)) {
                        throw std::out_of_range(
                            "argument index is out of range in format");
                    }
                    output += arg_strs[i];
                    index.clear();
                    state = COPYING;
                }
                else goto fail;
                break;

            case CLOSE_BRACE:
                if (c == '}') {
                    output += '}';
                    state = COPYING;
                }
                else goto fail;
                break;
        }
    }

    if (state != COPYING) goto fail;
    return output;

fail:
    throw std::invalid_argument("invalid format string");
}

template <class... Args>
void print(const std::string& fmt, Args&&... args)
{
    std::cout << format(fmt, std::forward<Args>(args)...);
}

int main()
{
    print("Hello, {0}! The answer is {1}.", "World", 42);
}

Here is a diagram of the FSM:

enter image description here

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I think CS subjects like automata are too much for this problem, thats more something you have to deal with when implementing a regular expressions engine. Here is some code in C# that I've written to replace tags in a string, its absolutely not optimal because the state is checked every iteration and each character is copied individually, but you'll get the my idea.

private string ReplaceTags(string text, Dictionary<string, string> tags)
{
    StringBuilder result = new StringBuilder();
    StringBuilder tag = new StringBuilder();

    int mode = 0;

    int len = text.Length - 1;

    for (int i = 0; i <= len; i++)
    {
        char c = text[i];

        if (mode == 0)
        {
            if (text[i] == '\\')
            {
                i++;

                if (i <= len)
                {
                    result.Append(text[i]);
                }
            }
            else if (text[i] == '[')
            {
                mode = 1;
            }
            else
            {
                result.Append(text[i]);
            }
        }
        else
        {
            if (text[i] == ']')
            {
                string _tag = tag.ToString().ToLowerInvariant();

                if (tags.ContainsKey(_tag))
                {
                    result.Append(tags[_tag]);
                }

                tag.Length = 0;
                mode = 0;
            }
            else
            {
                tag.Append(text[i]);
            }
        }
    }

    return result.ToString();
}
share|improve this answer
    
Poor guy's getting mixed signals for sure--he did the FSM because I advised it. We may be reaching the point of personal preferences--your code strikes me as less readable (and doesn't appear intended to solve the same problem). –  Jerry Coffin Jul 14 '14 at 14:07
    
@JerryCoffin - I'm advising a non-scientific approach to a non-scientific problem, I think that is a good signal. And it does solve the same problem, with the difference that this parser replaces strings instead of integers. –  Leopold Asperger Jul 14 '14 at 14:28
    
If you look through his code, you'll quickly realize that the problem you're dealing with is substantially simplified compared to the OP's. He's not only replacing numbers, but dealing with patterns like {{, {}, leading zeros on the numbers, etc. It strikes me as a little like saying "No reason for a compiler to use those fancy FSM things. I wrote something that parses mathematical expressions in only 100 lines, with none of that stuff." –  Jerry Coffin Jul 14 '14 at 14:32
    
@JerryCoffin - This parser handles escape sequences as well, remark unjustified. Remove leading zeros is not a big deal. And I'm not marking FSM as fancy, I'm implying that it is irrelevant in terms of implementation, especially for this simple problem. You could read many books describing the mathematical model of FSM and you will still not know what an implementation looks like. The length of your expression parser is meaningless. –  Leopold Asperger Jul 14 '14 at 14:56
    
My original implementation looked more like yours. Just lots of if/elses. I think that this new implementation is easier to read and understand, so I'm not sure what benefit there would be from not using the FSM approach. –  Chris_F Jul 15 '14 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.